경로 출력 말하시는 것이군요. 최단 거리는 출력하실 수 있으시고..

BFS를 쓰던, Heap을 이용한 Dijkstra를 쓰던. 뭘 쓰던지간에. 하나의 path를 탐색하면 아래의 정보가 쓰일 겁니다.

현재 i번째 노드에 있고, i번째 노드와 j번째 노드가 연결되어 있다. j가 방문되지 않았다. 그러면 j는 i로부터 온 것이기 때문에, j의 부모는 i가 됩니다.

BFS는 아시다시피.

(1) Queue애서 item을 dequeue 합니다. 이걸 nn이라고 하죠.

(2) dequeue한 item과 인접하면서, 방문하지 않은 노드들이 있다면 그것들을 탐색합니다.

(2)번 과정에서, 현재 탐색하는 노드들의 부모는, dequeue한 것이다. 이런 정보를 넣으면 되지 않을까요?

그리고 나서, 도착점부터, 시작점까지 거꾸로 역추적해서 올라가면 되겠죠.

예를 들어서, 예제 데이터 같은 경우 start = 1, end = 2입니다.

이 때 BFS를 돌려볼까요? 어디서부터 왔느냐 배열을 추가로 넣은 상태에서 말이죠.

(1) 1을 큐에 넣습니다.

queue = [1]

where_is_from = [-1, 0, 0, 0, 0]

(2) 1을 큐에 뺍니다. 그리고 1과 인접한 3, 5가 enqueue 됩니다.

queue = [3, 5]

where_is_from = [-1, 0, 1, 0, 1]

(3) 3을 큐에서 뺍니다. 그러면 3과 인접하면서 방문하지 않은 4만 걸립니다. 4를 큐에 넣습니다.

queue = [5, 4]

where_is_from = [-1, 0, 1, 3, 1]

(4) 5를 큐에서 뺍니다. 5와 인접하면서 방문하지 않은 노드는 없습니다.

queue = [4]

where_is_from = [-1, 0, 1, 3, 1]

(5) 4를 큐에서 뺍니다. 4와 인접하면서, 방문하지 않은 노드는 2입니다.

queue = [2]

where_is_from = [-1, 4, 1, 3, 1]

(6) 2를 큐에서 뺍니다. 도착점이니까 끝나겠군요.

where_is_from 배열을 어떻게 활용할 것인지는 잘 생각해 보세요.

아하! where_is_from배열이 어디에 사용되는지 알 것 같습니다. 조언 감사합니다.

chogahui05

너무너무나 친절한 설명 감사드려요!!!