Random Walk2

aka ScheduledWalk

aka = also known as

바퀴벌레 한 마리가 판 위를 돌아다닌다. 이 바퀴벌레가 각 칸을 방문한 횟수와 총 움직인 횟수를 구하라.

이 페이지에 있는 활동들은 프로그래밍과 디자인에 대해 생각해 볼 수 있는 교육 프로그램이다. 모든 활동을 끝내기까지 사람에 따라 하루에서 삼사일이 걸릴 수도 있다. 하지만 여기서 얻는 이득은 앞으로 몇 년도 넘게 지속될 것이다. 문제를 풀 때는 혼자서 하거나, 그게 어렵다면 둘이서 PairProgramming을 해도 좋다.

입력 ¶

표준입력을 통해 다음 내용을 입력 받는다.

M N
(0~(M-1)) (0~(N-1))
([0~7]*)
999

첫 줄의 M,N은 판의 행과 열로 판의 크기를 말하고, 다음 라인의 숫자 두 개는 바퀴의 초기 위치로 행과 열의 순서다. 다음 줄에는 바퀴의 여정이 나오는데 0부터 7 사이의 숫자가 이어진다. 0부터 7 사이의 숫자는 방향을 의미한다. 0이 북쪽이고, 시계방향으로 1,2,3,...7이 배치된다. 마지막 줄은 999로 끝난다.

예.

10 10
0 0
22222444445
999

10행 10열의 판의 0행 0열 지점에서 바퀴가 출발하고, 처음 다섯 칸을 동쪽으로 움직인 다음, 다섯 칸을 남쪽으로 움직이고, 마지막에 남서쪽으로 한 칸 움직인 다음 끝난다.

[edit]

종료 조건 ¶

판 위의 모든 칸(cell)을 한번 이상 방문했거나
바퀴벌레의 여정이 끝나거나

[edit]

진행 ¶

바퀴는 여정에 따라 한 번에 한 칸 씩 움직이되 총 8 방향 중 하나로 움직일 수 있다. 만약 판의 끝을 넘어서면 반대쪽으로 돌아 나오게 된다.
만약 열이 N-1일 때 동쪽으로 움직이면 같은 행의 0열로 이동하고, 열이 0일 때 서쪽으로 이동하면 동일 행의 N-1열로 나온다.
만약 행이 M-1일 때 남쪽으로 움직이면 같은 열의 0행으로 나오고, 행이 0일 때 북쪽으로 이동하면 동일 열의 M-1행으로 나온다.
따라서, 위치가 0행 0열일 때 북서쪽으로 움직이면 M-1행 N-1열로 나오게 된다.

[edit]

출력 ¶

표준 출력을 통해, 바퀴가 총 움직인 횟수와 각 칸에 도달한 횟수를 출력한다. 양식은 다음과 같다.

(총 횟수)

(n0,0) (n0,1) (n0,2) ... (n0,N-1)
(n1,0) (n1,1) (n1,2) ... (n1,N-1)
...
(nM-1,0) ...             (nM-1,N-1)

첫 번 째 줄은 바퀴가 총 움직인 횟수(처음 바퀴가 놓이는 것은 움직인 것으로 치지 않는다)이고 한 줄은 띈 다음, 판의 각 칸에 바퀴가 방문한 횟수를 행렬로 출력하되, 동일 행의 칸은 빈칸(스페이스)로 구분하고, 각 행은 하나의 줄을 차지한다.

예.

11

1 1 1 1 1 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

[edit]

Source ¶

해결자	개발시간	사용언어	Source
이상규	.	C++	RandomWalk2/상규
조현민	.	C++	RandomWalk2/현민
인수	.	C++	RandomWalk2/Insu
영동	.	C	RandomWalk2/영동
상규, 창섭	.	C++	ScheduledWalk/창섭&상규
재니, 영동	.	C++	ScheduledWalk/재니&영동
.	.	C	RandomWalk2/Vector로2차원동적배열만들기
석천	.	C++	ScheduledWalk/석천
신재동	.	Python	RandomWalk2/재동
상규, 신재동	2시간	Python	RandomWalk2/ExtremePair
조현태		C++	RandomWalk2/조현태

다음은 이상의 요구조건을 만족하는 프로그램 개발이 완료되었을 경우만 본다.

대부분의 프로그래밍 문제나, 경시대회 문제는 한번 주어진 문제에 한번 대응하면 그걸로 끝난다. 하지만 현실은 그렇지 못하다. 한번 개발한 프로그램을 요구사항 추가/변경에 따라 몇 번이고 수정하고 다시 개발해야 할 때도 있다. 우리가 말하는 문제풀이 능력에는 이미 만든 프로그램을 유지보수하는 작업도 포함되어야 한다.

교육에 있어 이런 작업이 중요한 이유 중 하나는, 자신이 만든 프로그램이 해답을 제대로 내느냐는 것을 확인하는 데에는 한 문제를 한번 푸는 것으로 족하지만, 거기서 코드의 디자인 질을 확인할 수가 없다는 문제가 있기 때문이다. 하지만, 요구사항 변경에 따라 자신이 개발한 프로그램을 다시 수정하게 되면, 이전에 만든 코드의 질에 따라 그 노력에 현격한 차이가 난다. 디자인 질이 높으면 아주 짧은 시간 안에 간단하게 요구사항 변화에 대응할 수 있을 것이고, 질이 낮았다면 장기간에 걸쳐 여기저기를 들쑤시고 골치를 썩혀야 할 것이다.

이런 경험을 하게 되면 "디자인의 질"이 무엇인가 직접 체험하게 되고, 그것에 대해 생각해 보게 되며, 실패/개선을 통해 점차 디자인 실력을 높일 수 있다. 뭔가 잘하기 위해서는, "이런 것이 있고, 난 그것을 잘 못하는구나"하는 "무지의 인식"이 선행되어야 한다. (see also

FourLevelsOfCompetence )

다음은 코드 디자인이 좋지 못했을 경우 고생을 할 요구사항 변경들이다. 그냥 대충 생각나는 대로 아무것이나 나열한 게 아니고, 순서나 변경사항이나 모두 철저하게 교육적 효과를 염두에 두고 "디자인"되었다.

변경사항은 순서대로 "누적적"이다. 변경1을 볼 때는 변경2를 보지 않는다. 현재의 변경을 모두 완료한 후에야 다음 변경을 볼 수 있다. 따라서 변경3을 하고 있다면, 사실상 현재의 코드는 기본 요구사항+변경1+변경2를 이미 충족하고 있어야 한다.

만약 자신이 작성한 코드를 위키에 올리고 싶다면 RandomWalk2/아무개 패턴의 페이지 이름을 만들고 거기에 코드를 넣으면 된다. 이 때, 변경사항을 하나씩 완료함에 따라, 코드의 어디를 어떻게 바꿨는지(예컨대, 새로 클래스를 하나 만들어 붙이고, 기존 클래스에서 어떤 메쏘드를 끌어온 뒤에 다른 클래스가 새 클래스를 상속하게 했다든지 등) 그 변천 과정과 자신의 사고 과정을 요약해서 함께 적어주면 자신은 물론 남에게도 많은 도움이 될 것이다. 또한, 변경사항을 하나 완료하는 데 걸린 시간을 함께 리포팅하면 한가지 척도가 될 수 있겠다.

[edit]

변경1 ¶

바퀴 커플

바퀴벌레의 마리수가 두마리로 늘어난다. 그리고 "턴"(turn)의 개념이 생긴다. 턴은 일종의 단위시간으로, 한번의 턴에 두 마리의 바퀴벌레는 각각 자신이 예정한 방향으로 이동을 한다.

입력자료는 다음과 같이 바뀌어야 한다.

10 10
0 0
22222444445
3 7
121212645372
999

첫번째 바퀴는 0행0열에서 22222444445의 여정으로 여행하고, 두번째 바퀴는 행7열에서 121212645372의 여정을 따른다. (두 바퀴의 시작점이 같을 수도 있다)

처음 턴에 1번 바퀴는 2방향으로 한칸 움직이고, 2번 바퀴는 1방향으로 한칸 움직인다. 둘 중 한쪽 바퀴의 여정이 끝나도 다른 하나의 바퀴 여정이 끝나지 않으면 게임은 종료하지 않는다. 하지만, 두 바퀴 중 어느 누구의 여정도 끝나지 않았더라도 판 위의 셀이 모두 방문되었다면(즉, 1이 방문한 셀과 2가 방문한 셀의 합집합이 전체 셀이라면) 게임은 종료한다.

출력정보는 각 바퀴별 움직인 수와 판의 상태가 된다.

(바퀴1)
(바퀴2)

(판의 상태)

[edit]

변경2 ¶

N-바퀴

바퀴는 총 N마리(N은 100 이하의 자연수)가 존재 가능하다. 방식은 위 바퀴 커플과 유사하다.

10 10
0 0
22222444445
3 7
121212645372
2 5
57575757575757575757
8 8
663
999

이 경우 총 네마리의 바퀴가 판 위를 돌아다니게 된다.

출력정보는 다음과 같다.

(바퀴1)
(바퀴2)
...
(바퀴N)

(판의 상태)

[edit]

변경3 ¶

슈퍼바퀴

바퀴에 두가지 종류가 있다. SuperRoach와 NormalRoach가 그것이다. NormalRoach는 한번에 한칸,SuperRoach는 한번에 두칸을 쓸고 지나간다.

입력자료는 다음과 같다.

10 10
0 0 S
22222444445
3 7 N
121212645372
2 5 N
57575757575757575757
8 8 S
663
999

첫번째 바퀴는 슈퍼바퀴로 0행0열에서 시작해서 22222444445의 여정대로 여행한다. 두번째 바퀴는 정상바퀴로 3행7열에서 여행을 시작한다.

어떤 슈퍼바퀴가 0행0열에서 출발하고 여정이 224였다면 그 바퀴가 지나간 판의 상태는 다음과 같다.

1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
...

출력정보는 바퀴별 움직인 횟수(슈퍼바퀴의 경우 한번에 두칸을 움직이기에 움직인 횟수 역시 두번으로 친다)와 판의 상태다. 앞서의 경우와 동일하다.
.

[edit]

변경4 ¶

쉬기,음식

이번에는 두가지의 요구사항 변경이 있다.

바퀴는 여정에서 9가 나오면 제자리에서 한 턴을 쉴 수 있다. 따라서 한 턴에 움직이는 바퀴는 전체 바퀴의 수 N보다 같거나 작다.

판 위에는 음식이 몇 군데 떨어져 있을 수 있다. 정상바퀴가 이 음식을 먹으면 다음 따라오는 일정기간(5턴) 동안 일시적 슈퍼바퀴가 된다. 태생적 슈퍼바퀴도 음식을 먹기는 하지만 자신에게는 아무 영향이 없다. 바퀴가 음식을 먹으면 그 셀의 음식 개수가 하나 줄어든다. 한 셀에 여러개의 음식이 있을 수 있다.

정상바퀴가 슈퍼바퀴가 된 동안에 다시 음식을 먹으면 "임시 슈퍼바퀴"의 기간이 현 시점에서 5턴만큼으로 재설정된다. 예컨대, 처음 음식을 먹고 슈퍼바퀴가 된 상태에서 2턴이 지난 다음에 다시 음식을 먹으면 앞으로 5턴 동안 슈퍼바퀴가 된다.

한 턴에 둘 이상의 바퀴가 동시에 음식이 있는 칸에 도착했을 때, 바퀴의 수가 음식의 수보다 많다면 바퀴들은 다음 순서로 음식을 먹는다.

정상바퀴
일시적 슈퍼바퀴
태생적 슈퍼바퀴
만약 우선순위가 같은 바퀴가 음식을 놓고 경쟁한다면 처음 입력했던 순서가 2차 우선순위가 된다.

입력자료는 다음과 같다.

10 10
2 6
3 9
4 8
4 7
-1
0 0 S
22222449944945
3 7 N
999121212645372
2 5 N
57597575757597597575757
8 8 S
663999
999

판의 크기는 총 10행10열이고, 2행6열, 3행9열, 4행8열, 4행7열에 음식이 미리 비치되어 있다(이 때 행과 열은 앞서와 마찬가지로 각각 0부터 시작). -1은 음식정보의 끝을 의미한다.

출력정보는 앞서와 유사하다. 한번에 두칸을 움직이면 움직인 횟수도 두번이고, 한번 쉴 때에는 움직인 횟수가 증가하지 않는다. (고로, 결국 "움직인 횟수"는 움직인 거리와 비슷하다고 보면 된다) 판의 정보는 예전과 동일한 양식으로 출력한다.
.

.
모든 요구사항 변경이 끝났다. 히딩크처럼 "여전히 배가 고프다"면, 이 게임을 삼차원(큐빅)으로 확장하는 것을 고려해 보라. 입력/출력자료의 스펙 등은 모두 자신이 판단해서 직접 정의하라. 어찌 되었건 여기까지 도달한 것을 진심으로 축하한다.

대부분의 학습자는 일단 문제의 답에 도달하면 그 경험을 완전히 망각해 버리는 나쁜 습관이 있다 -- 이런 사람들은 문제를 풀긴 풀었으되, 다음 번에 유사 문제를 접하면 여전히 그 문제를 처음 접했을 때를 답습하는 제자리 걸음을 하기 쉽다. 자신의 경험을 반추해 보는 것은 효과적인 학습에 있어 필수적인 요소다. 다음 활동을 꼭 해보길 권한다. 엄청나게 많은 것을 배우게 될 것이다.

[edit]

남 관찰/분석하기 ¶

다른 사람의 코드와 그 코드가 나온 과정을 가능하다면 구경하고 분석하라. 자신과의 차이점과 유사점은 무엇인가?

각 요구사항 변경에 다른 사람은 어떤 식으로 대응했는가?

자신이 사용한 방법과 비교해 보라. 누구의 것이 더 낫다고 생각하는가?

몇 몇 사람들이 공통적으로 사용하는 "좋은 접근법"과 "나쁜 접근법"이 있는가?

내 프로그램을, 또 그 진화의 과정을 남에게 보여주고 의견을 들어보라.

[edit]

새로하기 ¶

최초의 요구사항 제시 이후에 나온 변경사항들이 따라오지 않을 것이라 가정하고, 만약 이 RandomWalk2 문제를 다시 접했다면 어떻게 접근하겠는가. 어떤 과정을 거쳐서 어떤 프로그램을 개발하겠는가?

최초의 요구사항을 "새로 접했다"고 가정하고, 그리고 기존에 얻었던 "통찰"만을 간직한 채, (최초 요구사항에 대해서만) 이 문제를 다시 한번 풀어보라. (차후의 요구사항 변경에 대한 고려는 하지 말라.)

다른 프로그램이 나오는가? 시간은 얼마나 덜/더 걸리는가? 디자인은 어떻게 달라졌는가?

이와 비슷한 문제를 혹시 과거에 접해보았는가? 그 문제를 이제는 좀 다르게 풀것 같지 않은가? 그 문제와 RandomWalk2 경험에서 어떤 공통점/차이점을 끄집어 낼 수 있겠는가? 어떤 교훈을 얻었는가? 자신의 디자인/프로그래밍 실력이 늘었다는 생각이 드는가?

만약 이 문제의 모든 "요구사항+변경사항들"이 한 덩어리의 "최초 요구사항"으로 처음부터 한꺼번에 주어졌다면 자신은 어떻게 이 문제를 풀었을 것 같은가? 어떻게 문제에 접근했을 것이며, 어떤 과정을 거쳤을까? 또, 어떻게 푸는 것이 효율적일까?

다른 친구와 PairProgramming을 해서 이 문제를 다시 풀어보라. 그 친구는 내가 전혀 생각하지 못했던 것을 제안하지는 않는가? 그 친구로부터 무엇을 배울 수 있는가? 둘의 시너지 효과로 둘 중 아무도 몰랐던 어떤 것을 함께 고안해 내지는 않았는가?