두 갈래 이상의 길이에서 판단은 어떻게 되는건가요?

Question

두 갈래 이상 나뉘어진 구간(길이가 같다면)에서는 어떻게 판단하고 나아가는지 이해가 되지 않아 구글링을 좀 해봤는데 두 갈래로 나뉘어져 있는 구간은 큐에서 두 좌표를 모두 큐에 넣고 큐에서 하나씩 꺼내 그 지점과 근접한 방문하지 않은 지점을 방문하게 된다는데  글이 있더라구요 이 말이 알 것 같으면서도 잘 이해가 되지 않습니다. 두 갈래에서는 어떻게 판단하고 앞으로 나아가나요? 그냥 두갈래중 먼저 발견한 정점으로 가는 건가요? 파란점이 시작점이라고 할때 만약 위 오른쪽 아래 왼쪽 순서로 for문을 돌면 오른쪽 점을 먼저 발견하니까 오른쪽으로 가게되고 결국 막히게 되는데  일단 오른쪽으로 계속 이동하다가 막히게 되면  다음으로 갈 수 있는 아래쪽 점으로 이동하고 이런식으로 반복하여 최단경로를 찾게 되는건가요?

Rookiss · Answer

그렇지 않습니다.
말씀하신건 DFS 로직이고 BFS는 그렇게 동작하는게 아닙니다.

BFS에서는 우측으로 막힐 때까지 쭉~ 가는게 아니라
예약된 순서대로 하나씩 접근하기 때문에
실제 접근 순서는 위와 같습니다.
말 그대로 시작점에서 가까운 순서대로 하나씩 접근해보게 됩니다.

큐에다 예약하는 순서를 유심히 분석해보시기 바랍니다.
초창기에 시작점을 큐에다 넣고,
이를 다시 빼서 인근 지점 (거리가 1인 애들) 둘을 발견해서 다시 큐에 넣게 됩니다.
그 다음 1인 정점 하나를 빼서, 거리가 2인 애들을 발견하게 됩니다.
그렇다고 거리가 2인 애를 바로 방문하는 것은 아니고,
먼저 예약되어 있는 나머지 1도 방문을 한 다음에 2를 방문하는 것이죠.
이 부분이 처음 배울 땐 헷갈리는데 찬찬히 분석해보시기 바랍니다.

홍키 · Answer

제가 이해한게 맞을까요? 위 사진의 파란점이 시작점이고 위 오른쪽 아래 왼쪽 순서대로 for문을 돈다면 오른쪽 점을 먼저 발견하니깐 오른쪽으로 가다가 막혀있으니깐 다시 갈 수 있는 아래쪽으로 가는데 이러한 과정을 반복해서 갈 수 있는 점들을 저장하여 최단거리를 파악한다. 라고 이해했는데 맞을까요?

Rookiss · Answer

두 갈래 길이 있고, 그 두 길 모두 처음 발견하는거라면 둘 중 아무 쪽이나 선택해서 갑니다. (큐에 넣은 순서대로) 현재 bfs 테스트 코드에서는 인덱스 순서로 0~6 검사를 하니 인덱스가 낮은 애부터 방문하겠지만, 실제로 이 순서는 유동적으로 코드를 만들기 나름입니다. 두 갈래로 나뉘어져 있는 구간은 큐에서 두 좌표를 모두 큐에 넣고 큐에서 하나씩 꺼내 그 지점과 근접한 방문하지 않은 지점을 방문하게 된다는데  글이 있더라구요 bfs의 코드를 유심히 보면,  1) 큐에다가 방문 예약을 하고 2) 큐에서 꺼내 해당 지점을 방문하고 3) 방문 지점에 인근한 지점들 중, 방문하지 않은 지점을 다시 큐에 넣고 이런 반복 루틴으로 되어 있습니다. 그러니 큐에서 하나씩 꺼내, 그 지점과 근접한 '방문하지 않은' 지점을 방문하게 되겠죠.