BFS 관련 질문드립니다.

Question

해당 코드에서, 예를 들어 (1, 1) 지점 기준으로 상(빨) 하(초) 좌(빨) 우(초) 이런 식으로 뚫려 있는 길이 하, 우 총 두 지점이라고 가정했을 때 큐에 저장되는 지점은 총 두 곳이겠죠? (2, 1), (1, 2) 이렇게요.. 그렇게 한 번 for 문 사이클이 돌고나면, 다시 위로 올라가서 큐에서 먼저 발견한 지점(여기서는 (2, 1)) 을 꺼내서 현재 좌표로 넣고, 그 좌표 기준으로 또 for 문을 돌고..다 끝나고 나면 이제는 (1, 2) 지점을 꺼내서 이 기준으로 for 문을 돌면서 또 큐에 갈 수 있는 지점을 저장하고..   계속적으로 반복하다보면 결국 가장 처음에 발견한 갈 수 있는 지점 (2, 1) 과 (1, 2) 루트로 가다가 둘 중 한 루트는 빨간 벽으로 막혀서 더이상 진행이 불가능한 루트가 될 것이며..남은 한 루트는 계속 살아남으면서 갈 수 있는 지점을 '전부' 탐색 하므로 목표 지점에서 본다면 결국 해당 루트가 최단 경로가 되는 것이 맞나요?

Rookiss · Answer

네 그렇습니다.
하지만 BFS는 딱히 '최단거리'를 구하는 알고리즘이 아니라,
'가장 cost가 적은 경로를 우선으로 순차적으로 가다 보니, 마지막에 운 좋게 목표 지점이 있었다'에 가깝습니다.
즉 BFS 결과물을 역으로 분석해서 최단거리를 구할 수 있는 것이지
애당초 BFS에선 목표 지점의 개념이 없으므로 사방향으로 신나게 서칭을 합니다.