동적 계획법 : 보행자 천국 (카카오 코드 페스티벌 예선 2017 문제 풀이)

보행자 천국 (카카오 코드 페스티벌 예선 2017 문제 풀이)

 문제 내용 : 위와 같다. 도로의 맵이 2차원 배열로 주어지고 값으로 0~2 값이 저장되어 지나갈 수 있는 조건을 나타내게되며, 우측하단까지 도달하는 경우의 수를 찾는 문제다.

 입력 형식 : 배열의 크기 m, n과 배열 내부의 값 city_map을 받는다.

 출려 형식 : 출력은 시작점에서 도착점까지 도달할 수 있는 경우의 수를 출력하면된다.

 풀이 : 나는 result 함수에서 결과를 계산하도록 했다. 맵의 크기와 시작좌표 0, 0을 받게되고 추가로 방향 direction을 받았다. 열거형을 사용해서 이전에 진행해오던 방향을 받았다. 왜냐하면 2인경우에 오던 방향으로만 갈 수 있기 때문에 진행방향을 받는다.

 코드 9라인에서 map의 범위를 초과하지 않게 검사한다. 14라인은 현재 검사되고 있는 곳이 도착점. 즉 우측 하단인 경우에 answer에 1을 대입한다. 이후에 18~24라인에서 재귀적으로 우측으로 또는 좌측으로 이동하면서 경우의 수를 더한다.

 18라인에서 1인경우 즉 막혀있는 경우에는 계산하지 않도록 했다. 19,22라인에서는 각각 우측이동 하측이동의 경우이다. 이때는 만약 2인경우 진행해 오던 방향이 옳바른 방향일 경우에만 이동을 진행하도록 했다.

 메인함수에서 결과를 출력해서 맞는 결과인 2가 뜨는 것을 확인할 수 있었다.

마치며

출제자의 해설에 따르면 동적 계획법(Dynamic programming)을 사용해서 풀 수 있는데 이 때 오른쪽으로 갈 수 있는 경우의수의 배열, 아래로 갈 수 있는 경우의 수 배열을 정의한 뒤에 채워나가는 식으로 풀면된다고한다. 나는 해설을 먼저 보지않고 풀었다. 그래서 아마 나의 코드를 제출하게 될 경우 pass가 안될 수도 있겠다.

 이는 구글에 검색하면 'Jaejin Jang'이라는 분의 블로그에 있는 풀이과정을 참고하면된다.

code.txt

2018/07/30 - [algorithm] - Flood fill 알고리즘 (카카오프렌즈 컬러링북 문제 풀이)