6108 : BFS 최단 거리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개와 간선 E개로 구성된 무가중치 무방향 그래프가 주어집니다. 시작 노드 S에서 목표 노드 T까지 도달하기 위한 최단 거리를 구하는 프로그램을 작성하십시오.
간선의 가중치가 모두 1이므로, 큐(Queue)를 사용하는 너비 우선 탐색(BFS) 기법을 이용하면 O(V+E) 시간 복잡도 내에 최단 경로를 보장하며 해결할 수 있습니다.
간선의 가중치가 모두 1이므로, 큐(Queue)를 사용하는 너비 우선 탐색(BFS) 기법을 이용하면 O(V+E) 시간 복잡도 내에 최단 경로를 보장하며 해결할 수 있습니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 E (0 ≤ E ≤ 10,000)가 주어집니다.
둘째 줄부터 E개의 줄에 걸쳐 간선을 연결하는 두 정점 u, v가 주어집니다.
마지막 줄에는 시작 노드 S와 목표 노드 T가 주어집니다.
둘째 줄부터 E개의 줄에 걸쳐 간선을 연결하는 두 정점 u, v가 주어집니다.
마지막 줄에는 시작 노드 S와 목표 노드 T가 주어집니다.
출력 설명
S에서 T까지 가는 최단 거리를 출력합니다. 도달할 수 없다면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
1 2
1 3
2 4
3 4
1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
시작 정점 S를 큐에 넣고 방문 처리(거리 0)한 후, 큐에서 하나씩 꺼내어 인접하고 아직 방문하지 않은 이웃 노드들을 방문(이전 노드의 거리 + 1)하면서 목표 정점에 도달하는 최초 시점에 거리를 반환합니다.