미로 탐색

백준 2178 미로 탐색 (BFS, 최단 경로 탐색, 행렬그래프)

이번 문제는 BFS를 어떻게 최단경로로 활용할건지 이해해야한다. 처음에는 나도 BFS로 어떻게 최단경로를 구한다는 소리인지 알 수 없었다. 나도 완벽하게 이해하고 풀지 않았기 때문에 생각의 흐름을 나열해 볼까 한다. 우선 행렬그래프를 BFS의 트리 형태로 나열한다고 가정한다면 다음과 같은 그래프를 만들 수 있다. 그렇다면 우리는 (4,4)가 되기 위해서 7층까지 내려가야한다는 것을 단숨에 확인 가능하다. 그렇다면 BFS로 탐색을 하면서 언제가 몇층인지를 알아야한다. 따라서 층을 함께 표기해본다. 그러면 (1,1)이 1층인것을 알기 때문에 층에 큐에 넣은 인접 행렬에 대해서 2층이라는 것을 표기하여 큐에 삽입할 수 있다. 이러한 방식으로 (4,4)까지 진행하면 간단히 (4,4)가 7층에 있는 것을 알 수 ..