[Python] 최단 거리 구하기(BFS)

문제 기술

n(1이상 1000이하 정수)개의 지하철 역(0부터 n-1까지 번호가 붙여져 있음)과 인접한 역의 쌍들이 주어져 있다. 두 지하철 역 a와 b에 대하여 a로부터 b로 가는 가장 짧은(지나는 에지 수가 가장 작은) 경로의 길이(지나는 에지의 수)를 구하는 프로그램을 작성하시오.

요구조건: 지하철 망을 인접리스트로 나타내고, 탐색방법은 너비우선탐색을 이용한다.

 

입력

첫 번째 줄에 지하철 역 수 n(1이상 1,000이하 정수)이 주어지고 두 번째 줄에 인접한 역들의 쌍의 수 m(0이상 30,000이하 정수)이 주어진다. 다음 m 개의 각 줄에 인접한 두 역 번호(0이상 n-1이하 정수가 빈칸을 사이에 두고 주어진다. 마지막 줄에 두 지하철 역 번호 a, b가 주어진다.

 

n m  // 지하철 역 수, 선로  수
u v  // 도시 u와 v사이에 선로가 있음
....
a b // 시작점 a, 목적지 b

출력

지하철 역 a로부터 지하철 역 b로 가는 가장 짧은 경로의 길이(지나는 에지의 개수)를 출력한다. 만약 가는 경로가 없으면 –1을 출력한다. 

입력 예

6 5 // 지하철 역 수, 선로 수  
1 2 
2 3
3 4
3 1
0 5
4 1    // a와 b

출력 예

2 // 4로부터 1까지의 최단 경로 길이 ( 4 - 3 - 1이라서 2가 되는 것이다. )

나의 코드

이전 문제와 마찬가지로 10행까지의 코드를 통해 이중 리스트 형태의 인접 리스트를 구현했고, bfs 함수의 매개변수로 시작 역과 끝 역, 그리고 방문 여부를 검사하는 visited를 넣었다.

distance는 우선 n개의 역 전부에 대해 0 처리를 하였고,  큐에 시작 값을 넣고 시작했다. 

큐가 있는 경우, 우선 popleft로 빼준 뒤 그 값의 인접 리스트들에 대해서

인접 리스트 내에 우리가 가야 할 목적지 destination이 있는 경우: w를 아예 destination으로 설정했다. 즉 가야 할 지점을 아예 명시를 해 둔 것이다.

그리고, 방문하지 않았을 경우 방문해주고, 큐에 넣어주고, distance를 1 더해준다.

w가 destination일 경우.. 큐를 비워주고 그 w까지의 거리인 distance[w]를 리턴한다.

결국 도달하지 못하는 경우에는 -1을 출력하도록 했다.

 

이 문제는, '최단 거리'만 구하는 것이기 때문에 쉽다. 그렇지만, 그 최단 거리에 해당하는 경로의 값들을 전부 출력하라고 한다면(예를 들어 위 입력 및 출력 예의 경우 4, 3, 1을 출력하는 것이다.) 문제의 난이도가 올라간다.

어쨌든, 최단 거리만을 구하는 것은 그냥 distance를 새로 옮겨가는 지점마다 전부 1씩 더해주기만 하면 되는 것이었기 때문에 어렵지 않게 풀 수 있었다.

코드는 여기에 있다.