에지의 가중치가 10 이하의 자연수인 방향 그래프가 있다. 이 그래프의 시작점에서 다른 모든 노드로의 최단 경로를 구하시오.
(시간 제한 2초)
입력
1번째 줄에 노드의 개수 V와 에지의 개수 E가 주어진다(1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000). 모든 노드에는 1부터 V까지의 번호가 매겨져 있다. 2번째 줄에 출발 노드의 번호 K가 주어진다.(1 ≤ K ≤ V). 3번째 줄에는 E개의 줄에 걸쳐 각 에지의 정보(u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 에지가 존재한다는 뜻으로, u와 v는 서로 다르다. 두 노드 사이에 에지가 2개 이상 존재할 수 있다는 것에 유의하자.
출력
1번째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 노드까지 최단 경로값을 출력한다. 시작점은 0, 경로가 없을 때는 INF를 출력한다.
예제 입력
5 6 // 노드 개수, 에지 개수
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
예제 출력
0
2
3
7
INF
1단계 - 문제 분석하기
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로, 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지를 묻고 있다.
2단계 - 손으로 풀어 보기
1 인접 리스트에 노드를 저장하고 거리 배열을 초기화한다.
2 최초 시작점을 큐에 삽입하고, 다익스트라 알고리즘을 수행한다.
- 거리 배열에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다.
- 해당 노드와 연결된 노드들의 최단 거리값을 다음 공식을 이용해 업데이트한다.
- Min(선택 노드의 거리 배열 값 + 에지의 가중치, 연결 노드의 거리 배열 값)
- 배열의 값이 업데이트된 경우 연결 노드를 큐에 삽입
- 큐가 빌 때까지 1 ~ 2를 반복한다.
3 완성된 거리 배열의 값을 출력한다.
3단계 - sudo코드 작성하기
V(노드 개수) E(에지 개수)
A(그래프 정보 저장 리스트)
distance(최단 거리 저장 배열)
visited(방문 저장 배열)
K(출발 노드)
for(노드 개수만큼 반복)
{
그래프 정보 저장 리스트 초기화
}
최단 거리 저장 배열 초기화(출발 노드는 0, 나머지는 적당한 큰 수)
방문 저장 배열 초기화
for(에지 개수만큼 반복)
{
그래프 정보 저장 리스트에 저장
}
우선순위 큐 생성
큐에 시작 노드 삽입
while(큐가 빌 때까지)
{
선택 노드 = 큐에서 poll
선택 노드 방문 체크
for(선택 노드에서 갈 수 있는 노드 개수만큼 반복)
{
if(연결 노드 거리 값 > 선택 노드 거리 값 + 에지 가중치)
{
거리 저장 배열[연결 노드] = 선택 노드 거리 값 + 에지 가중치
큐에 연결 노드 추가
}
}
}
거리 배열의 값 출력(초기화한 큰 수에서 바뀌지 않은 수는 INF 출력)4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Q56 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
ArrayList<Edge56>[] A = new ArrayList[V+1];
for(int i = 1; i < V+1; i++){
A[i] = new ArrayList<Edge56>();
}
for(int i = 0; i < E; i++){
st = new StringTokenizer(br.readLine());
int startNode = Integer.parseInt(st.nextToken());
int endNode = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
A[startNode].add(new Edge56(endNode, value));
}
int[] distance = new int[V+1];
for(int i = 1; i < V+1; i++){
distance[i] = Integer.MAX_VALUE;
}
distance[K] = 0;
boolean[] visited = new boolean[V+1];
for(int i = 1; i < V+1; i++){
visited[i] = false;
}
PriorityQueue<Edge56> queue = new PriorityQueue<Edge56>();
queue.add(new Edge56(K,0));
while (!queue.isEmpty()) {
Edge56 now = queue.poll();
int now_Node = now.targetNode;
if(visited[now_Node])
continue;
visited[now_Node] = true;
for(int i = 0; i < A[now_Node].size(); i++){
Edge56 tmp = A[now_Node].get(i);
int next_Node = tmp.targetNode;
int value = tmp.value;
if(distance[next_Node] > distance[now_Node] + value){
distance[next_Node] = distance[now_Node] + value;
queue.add(new Edge56(next_Node, distance[next_Node]));
}
}
}
for(int i = 1; i < V+1; i++){
if(distance[i] == Integer.MAX_VALUE)
System.out.println("INF");
else
System.out.println(distance[i]);
}
}
}
class Edge56 implements Comparable<Edge56>{
int targetNode;
int value;
Edge56(int targetNode, int value){
this.targetNode = targetNode;
this.value = value;
}
@Override
public int compareTo(Edge56 o) {
return this.value - o.value;
}
}
- Do it! 알고리즘 코딩테스트 자바 편
