[백준] 1600 말이 되고픈 원숭이

---

원숭이가 (0, 0) 지점에서 (W-1, H-1)까지 이동하는 이동 횟수의 최소값을 구하는 문제이다.

 

처음 문제를 접하고 DP를 사용하면 해결 할 수 있을 것 같아 시도하였지만, 해결하지 못했다. 다른 풀이를 보니 BFS로 해결할 수 있었다. 

 

먼저 DP로 왜 해결할 수 없었는 지에 대해서 설명한다.

 

입력

1
6 6
0 1 1 1 1 0
0 1 1 1 1 0
0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
1 0 0 0 1 0

출력(정상)
8

위 값이 입력으로 주어져 DFS & DP 를 수행하면 중간 지점에 아래와 같은 결과가 출력된다.

[0, 0, 0, 0, 0, 11]
[1, 0, 0, 0, 0, 10]
[2, 3, 8, 9, 8, 9]
[0, 4, 7, 8, 9, 10]
[0, 5, 6, 7, 8, 0]
[0, 6, 7, 8, 0, 10]

DP[6][6]의 값은 반드시 DP[4][5] 또는 DP[5][4]을 통해 갱신되어야 한다. 현재 DP[6][6]의 값은 DP[4][5]의 값으로 인해 갱신 되었다. 이때 DP[5][4]의 값을 보면 7로 갱신 되어 있기 때문에 다음에 DP[6][6]의 값이 8로 갱신 되어야 할 것 같다.

 

하지만 DP[5][4]의 값은 다시 DP[5][3] 또는 DP[6][2]의 값을 통해 갱신 되었을 것 인데, 만약 DP[6][2]의 값을 통해 갱신되었다면 이미 말과 같은 위치 이동을 한번 사용했기 때문에 DP[6][6]은 8로 갱신될 수 없다.

 

그리고 DP[5][3] + 1 = 7이기 때문에 DP[5][4]가 다시 갱신될 수 없어 DP[6][6]은 10을 값으로 가지게 된다.

 

이를 해결하기 위해 >= 비교를 할 수 도 있지만, 너무나 많은 연산을 요구하기 때문에 시간초과가 발생한다.

 

 

 

BFS를 통해 해결하기 위해서는 (r, c, k) 값에 따른 3차원 배열을 통해 해결할 수 있다.

 

Python