원래 지난주에 정리하려고 했는데, 개인적인 이슈로 인해 오늘 적는다
https://www.notion.so/2-377d7702def0489d90c1e46ac34bb838 ( 접근 불가 개인 노션 )
문제 풀이
처음에는 이 문제가 디익스트라 문제라고 생각했다.
모든 노드 각각에서 부터 “하나의 노드" 까지의 최소거리들을 모두 알아야 하는 것 이라고 생각했기 때문이다.
하지만
디익스트라로 하니까 시간초과가 나왔다ㅏ.
import java.util.*;
class Solution {
private List<List<Integer>> graph = new ArrayList<>();
public int[] solution(int n, int[][] roads, int[] sources, int destination) {
int[] answer = {};
initGraph(n, roads);
int[] d = dikstra(destination, sources, n);
answer = minimums(d,sources);
return answer;
}
private void initGraph(int n, int[][] roads) {
graph = new ArrayList<>(n+1);
for(int i =0 ;i <=n;i++) {
graph.add(new ArrayList<>());
}
for (int[] road : roads) {
graph.get(road[0]).add(road[1]);
graph.get(road[1]).add(road[0]);
}
}
private int[] dikstra(int destination, int[] sources,int n) {
PriorityQueue<Node> pq = new PriorityQueue<>();
int[] d = new int[n+1];
Arrays.fill(d,Integer.MAX_VALUE);
d[destination] = 0; // 시작점
pq.add(new Node(destination,0)); // 노드 번호, 비용
while(!pq.isEmpty()) {
Node min = pq.poll();
// 여기는 모든 간선이 다 동일하게 1 이라서, pq 에서 빼내서 또 다시 , 현재 거리 테이블의 최소거리보다 작거나 같은지 확인하는 과정이 불필요
for (Integer i : graph.get(min.getN())) {
if(min.getW() + 1 < d[i]) { // 현재 최소거리 테이블보다 작은 비용이 들게 될 것인지 확인
d[i] = min.getW() + 1;
pq.add(new Node(i, d[i]));
}
}
}
return d;
}
private class Node implements Comparable<Node>{
private final int n;
private final int w;
public Node(int n, int w) {
this.n = n;
this.w = w;
}
@Override
public int compareTo(Node o) {
return o.w - this.w;
}
public int getN() {
return n;
}
public int getW() {
return w;
}
}
private int[] minimums(int[] d, int[] s) {
int[] result = new int[s.length];
for(int i =0;i<s.length;i++) {
if (d[s[i]] == Integer.MAX_VALUE) {
result[i] = -1;
} else {
result[i] = d[s[i]];
}
}
return result;
}
}위와 같은 디익스트라로 할 게 아니라, destination 에서만 출발하는 bfs 로 하는게 맞을 듯 하여 시도해보니 풀렸다.
- 어떻게 bfs 로도 가능한가요?
- bfs 는 breadth first search 이기 때문에, 같은 depth 에 있는 모든 노드들을 우선 방문한다. 따라서 하나의 노드에서부터 타고 내려간다고 생각하면, “ 그 노드" 로부터 다른 노드들을 방문한다고 볼 수 있다. 그리고 이 경우, 다른 모든 노드들에 대해 최소 비용으로 방문하게 되는 것이기 때문이다.
- 왜 비용이 더 적게 들죠?
- 위의 디익스트라는 PQ 를 사용한 방식이기 때문에 O((E+V)logV) 이다.
- bfs 의 경우 O(E + V) 의 시간복잡도를 갖는다.
- 따라서 V 가 2 보다 작지 않은 이상 디익스트라의 시간복잡도가 bfs 의 것보다 더 작아질 수가 없당
import java.util.*;
class Solution {
private List<List<Integer>> graph = new ArrayList<>();
public int[] solution(int n, int[][] roads, int[] sources, int destination) {
int[] answer = {};
initGraph(n, roads);
Map<Integer, Integer> map = bfs(destination, n);
answer = new int[sources.length];
for(int i =0;i< sources.length;i++) {
answer[i] = map.getOrDefault(sources[i],-1);
}
return answer;
}
private void initGraph(int n, int[][] roads) {
graph = new ArrayList<>(n+1);
for(int i =0 ;i <=n;i++) {
graph.add(new ArrayList<>());
}
for (int[] road : roads) {
graph.get(road[0]).add(road[1]);
graph.get(road[1]).add(road[0]);
}
}
private Map<Integer, Integer> bfs(int start, int n) {
Deque<int[]> q = new ArrayDeque<>();
Map<Integer,Integer> map = new HashMap<>();
boolean[] visit = new boolean[n+1];
visit[start] = true;
map.put(start,0);
q.add(new int[]{start, 0});
while(!q.isEmpty()){
int[] cur = q.poll();
for (Integer adj : graph.get(cur[0])) {
if(visit[adj]) continue;
visit[adj] = true;
int d = cur[1]+1;
q.add(new int[]{adj,d});
map.put(adj, d);
}
}
return map;
}
}