6120 : 양방향 BFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
엄청나게 큰 정점 N과 간선 M을 가진 그래프에서 시작 노드 S에서 목표 노드 T까지의 최단 거리를 구하려 합니다.
탐색 공간을 줄이기 위해, 시작점 S에서 뻗어나가는 탐색과 끝점 T에서 뻗어나가는 탐색을 병렬로 수행하여 두 탐색 전선이 만나는 시점을 찾아 최단 거리를 결정하는 양방향 너비 우선 탐색(Bidirectional BFS) 원리를 이해하고 구현해 보십시오.
탐색 공간을 줄이기 위해, 시작점 S에서 뻗어나가는 탐색과 끝점 T에서 뻗어나가는 탐색을 병렬로 수행하여 두 탐색 전선이 만나는 시점을 찾아 최단 거리를 결정하는 양방향 너비 우선 탐색(Bidirectional BFS) 원리를 이해하고 구현해 보십시오.
입력 설명
첫째 줄에 N (1 ≤ N ≤ 100,000)과 M (0 ≤ M ≤ 200,000)이 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S와 목표 노드 T가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S와 목표 노드 T가 주어집니다.
출력 설명
S에서 T까지의 최단 거리를 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 2
2 3
1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
시작 측 큐와 끝지점 측 큐를 따로 관리하고 각각 방문 표시를 합니다. 매 턴마다 크기가 더 작은 큐 측을 확장시키면서, 상대방 큐에서 이미 방문했던 노드를 조우하면 탐색을 멈춥니다.