백준 17835번 면접보는 승범이네 JAVA

요구사항 정의

• 모든 도시에 대해, 면접장까지의 최단거리 중 가장 거리가 먼 도시를 찾음
• 도로는 단방향이며 도시와 도시 사이에 여러 개의 도로가 있을 수 있음

 

제약 조건

• N(2 ≤ N ≤ 10^5): 도시의 개수
• M(1 ≤ M ≤ 5*10^5): 도로의 개수
• K(1 ≤ K ≤ N): 면접장의 개수

 

풀이 방법

다익스트라가 시작점부터 끝점까지의 최솟값을 구하는 알고리즘이지만

N개의 도시에 대해서 모두 다익스트라를 돌리면 O(N^2MlogN)의 시간복잡도가 나오게 된다

 

눈치로 그럼 면접장부터 시작하는 다익스트라인 것을 알았지만,

이 방법이 시간복잡도가 안터진다는 것을 확신할 수는 없었다.

O(NMlogN)도 터지는 것아닌가? 

 

다익스트라의 시간복잡도를 잘못 알고있었다...

처음 시도가 O(NMlogN) 이고,

면접장부터 다익스트라를 돌리는 방식은 O(MlogN)이다. 

 

 

이외에도 생각할게 많았다...

 

1. 최단 거리의 최댓값

최단 거리의 최댓값이 int 범위를 넘어서 실패하는 케이스가 있었다.

다익스트라에서 어떻게 오버플로우 여부를 체크할까.. 

 

연속해서 N개의 도시를 지나가는데 모든 도시 간 거리가 C라면
최댓값은 MAX(N)*MAX(C)  = 10^5 * 10^5 = 10^10

따라서 int의 최대 범위인 10^9를 초과하므로 long을 사용해야함

 

2. 도시 간 여러 개의 경로 존재

 

문제의 요구사항에서 "도시 간의 경로는 여러 개 있을 수 있다"라고 명시함

A->B 경로가 여러 개 있을 수 있다는 것!

 

그렇기 때문에 큐에서 꺼냈는데 이미 더 짧은 값으로 갱신되어있으면 굳이 더 할 필요가 없다

오히려 시간초과의 위험이 있을 수 있음

if(dist[curr.curr] < curr.cost) continue;

 

노드 간의 간선이 여러 개라면 꼭 추가하자

 

 

코드