최단 경로
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 12번째.
start에서 end까지 가는 데 필요한 최소 간선의 수는 몇 개일까요? 가중치가 없는 그래프(모든 간선의 비용이 동일함)에서, 그 답은 바로 BFS가 계산하는 것입니다. BFS는 시작 지점으로부터 거리가 증가하는 순서대로 정점을 방문하기 때문에, 처음으로 end에 도달했을 때가 바로 최단 경로를 따라간 것입니다.
비결은 각 정점을 지금까지의 거리와 함께 큐에 넣는(enqueue) 것입니다. (start, 0)으로 시작하세요. 거리가 d인 정점에서 새로운 이웃 v를 발견할 때마다, (v, d + 1)을 큐에 넣으세요. v == end일 때, d + 1을 반환합니다.
두 가지 예외 상황이 있습니다. 만약 start == end라면, 답은 0입니다. 만약 BFS가 end에 도달하지 못하고 종료된다면, 두 정점은 서로 다른 연결 성분에 있는 것이며, 답은 -1입니다.
챌린지
쉬움2차원 정수 배열 adjacency, 정수 start, 그리고 정수 end를 입력받아 start에서 end까지의 최단 거리(간선 수)를 반환하는 함수 shortestPath를 작성하세요.
- 만약
start == end이면,0을 반환합니다. - 만약
start에서end에 도달할 수 없으면,-1을 반환합니다. - 그렇지 않으면, 두 지점 사이의 최소 간선 수를 반환합니다.
반드시 Graph 클래스를 사용해야 합니다 (graph에 제공됨). 인접 리스트를 모델링하기 위해 언어 내장 기능(맵, 셋)을 사용하지 마세요. 알고리즘을 위한 보조 데이터(방문 확인용 셋, 큐 등)는 표준 라이브러리 타입을 사용할 수 있습니다.
직접 해보기
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}