[2178] 미로 탐색

---

BFS를 이용해서 최단경로를 구하는 기초 문제라고 할 수 있다.

하지만 아직 BFS를 공부하는 나의 입장에서는 어려워서 고민이 많았다.

내가 고민했던 부분은 BFS를 이용해서 모든 경로를 탐색하는 것은 쉽지만 "어떻게 최단 거리를 구하냐 ?" 이다.

위의 예제에서 내가 헷갈렸던 부분을 한번 정리 해보자.

4 6

1 0 1 1 1 1

1 0 1 0 1 0

1 0 1 0 1 1

1 1 1 0 1 1

내가 고민했던 부분은 위의 예제에서 (0,4)까지는 길이 1개이기 때문에 탐색을 쉽게했지만 어떻게 오른쪽으로 갈지 밑으로 갈지

판단하는 것이 고민되었다. 오른쪽으로 갔다가 다시 왼쪽으로 돌아와서 밑으로 가야하나 아니면 애초에 더짧은 밑에 길을

선택해서 가게 코드를 짜야하나 고민했다. 하지만 그런 방법은 내 머리에서는 도저히 찾을 수 없었고, 아무리 고민해도

답이 나오지 않아 결국 다른 사람의 답을 검색해서 참조해서 알아내었다.

핵심 코드는 map[nextX][nextY] = map[currentX][currentY]+1; 인데, 

다음에 갈 방향 좌표를 현재좌표에서 1씩 더하면서 그 좌표에 도달했을 때 거리를 계산해주는 것이다.

위의 코드대로 map을 바꾸고 마지막에 출력해보면 아래와 같은 결과가 나온다.

                                                                          1 0 9 10 11 12 

                                                                          2 0 8  0  12  0 

                                                                          3 0 7  0  13 14 

                                                                          4 5 6  0  14 15 

즉, 11번째에서 다음 12번째 거리로 갈 때 각각의 좌표를 현재좌표에 1씩 더해줘서 거리를 저장하는 것이 핵심이었다.

13에서도 보면 오른쪽과 밑이 각각 14로 저장되고, 각각의 14의 오른쪽과 밑은 15로 저장되어

최단거리가 결국 15로 저장되는 것을 알면 문제를 해결할 수 있다.