BFS(너비 우선 탐색) - 최단 경로 찾기

PATH <c1> <c2>: 두 커밋 사이의 가장 짧은 연결(간선 수 최소)을 찾습니다. 단, 커밋-부모 연결을 무방향(양방향으로 오갈 수 있는) 간선으로 봅니다.

BFS = 시작점에서 출발해서 가까운 이웃부터 차례차례 넓혀가며 탐색. 성질: BFS는 처음 도달했을 때가 곧 최단 거리입니다.

필요한 도구:

• 큐(queue): 다음에 방문할 곳 목록. 먼저 넣은 것부터 꺼냄 (collections 금지지만 list의 append/pop(0) 또는 인덱스 포인터로 구현 가능)
• visited 집합: 이미 방문한 커밋 재방문 방지 (사이클 대비)

경로 복원: 큐에 넣을 때 "어디서 왔는지(came_from)"를 기록해두면, 도착점에서 시작점까지 거꾸로 따라가며 경로를 만들 수 있습니다.

동률 처리(요구사항): 최단 경로가 여러 개면 hash1->hash2->... 문자열 기준 사전순 최소 선택. 구현 팁: 이웃을 방문 예약할 때 해시 문자열 순으로 정렬하거나, 같은 거리의 후보들 중 사전순으로 앞선 것을 우선 선택하도록 처리.

---

출처: Codyssey-B1/B5-2