문제
https://school.programmers.co.kr/learn/courses/30/lessons/132266
입력
강철부대가 위치한 지역을 포함한 총지역의 수 n,
두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads,
각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources,
강철부대의 지역 destination
출력
sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간
풀이
제한조건
- 3 ≤ n ≤ 100,000
- 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
- 2 ≤ roads의 길이 ≤ 500,000
- roads의 원소의 길이 = 2
- roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
- 동일한 정보가 중복해서 주어지지 않습니다.
- 동일한 [a, b]가 중복해서 주어지지 않습니다.
- [a, b]가 있다면 [b, a]는 주어지지 않습니다.
- 1 ≤ sources의 길이 ≤ 500
- 1 ≤ sources[i] ≤ n
- 1 ≤ destination ≤ n
접근방법
IDEA 1. 플로이드워셜
sources의 각 원소에서 destination 까지의 최단거리를 모두 구해야 한다.
여러 정점에서 거리를 구해야 하기 때문에 처음 떠올랐다.
하지만 n의 크기가 10만으로 플로이드 워셜을 구현하기에는 시간적으로 문제가 있다고 판단했다.
IDEA 2. 다익스트라
조금 더 단순하고 시간복잡도 상으로 넉넉한 다익스트라가 떠올랐다.
하지만 이 문제에서는 모든 간선간의 가중치가 1이므로 굳이 다익스트라를 사용할 필요가 없다. 조금 더 단순한 방법으로 선택하기로 했다.
불가능 한 방법이 아님
IDEA 3. BFS
모든 간선의 가중치가 1이기 때문에 BFS의 결과가 곧 최단거리이다. 또한 위의 두 알고리즘보다 단순하고 구현도 빠르다.
그럼 IDEA 1에서 처음 생각했던
sources의 각 원소에서 destination 까지의 최단거리만 해결하면 된다.
그럼 각 원소마다 탐색을 해서 detination까지의 거리를 찾아야할까?
최대 500번의 BFS 탐색으로, 각 탐색마다 모든 간선을 돌며 찾아야 하는가? 라는 생각이라면 플로이드 워셜을 왜 포기했는지 다시 떠올려야 한다.
destination이 1개로 주어지기 때문에
destination에서 BFS 탐색을 한 번만 수행하면,
sources의 각 원소까지의 최단 거리를 구할 수 있다.
코드
import java.util.*;
class Solution {
int[] cost;
List<Integer>[] graph;
public int[] solution(int n, int[][] roads, int[] sources, int destination) {
graph = new List[n + 1];
for(int i = 0 ; i <= n; ++i)
graph[i] = new ArrayList();
for(int[] data : roads){
// 양방향 연결
graph[data[0]].add(data[1]);
graph[data[1]].add(data[0]);
}
cost = new int[n + 1];
Arrays.fill(cost, -1); // 경로가 없는 경우 -1 출력하기 위함.
search(destination);
int[] answer = new int[sources.length];
for(int i = 0; i < sources.length; ++i)
answer[i] = cost[sources[i]];
return answer;
}
public void search(int start){
Queue<Integer> q = new ArrayDeque();
q.add(start);
cost[start] = 0;
while(!q.isEmpty()){
int cur = q.poll();
int len = graph[cur].size();
for(int i = 0; i < len; ++i){
int next = graph[cur].get(i);
if(cost[next] == -1){
cost[next] = cost[cur] + 1;
q.add(next);
}
}
}
}
}