[BOJ] 백준 1753 최단거리

출처:  https://www.acmicpc.net/problem/1753

 Input 

5 6

1

5 1 1

1 2 2

1 3 3

2 3 4

2 4 5

3 4 6

 

 Output 

0

2

3

7

INF

음의 가중치가 없기 때문에 다익스트라(Dijkstra) 이용.

다익스트라 (Dijkstra)

▶ 그래프 구현 (인접 리스트 / 인접 행렬)

그래프 표현 (인접 리스트 / 인접 행렬)

- 정점의 개수(N) 1 ≤ N ≤ 20,000, 간선의 개수(M) 1 ≤ M ≤ 300,000 이므로

  그래프를 인접행렬로 표현하면 메모리 초과 발생하기에 인접리스트로 구현

- 서로 다른 두 정점간 여러 경로가 주어질 때, 인접행렬의 경우 데이터처리를 해주어야 하지만,

   인접리스트의 경우 다익스트라 알고리즘에서 최적 경로를 처리하므로 Input Data에 대해 별도 처리 불필요.

※ 인접행렬로 처리한 문제: - [BOJ] 1916 최소비용 구하기 

[BOJ] 백준 1916 최소비용 구하기

 

② 우선순위 큐 이용. → 시간 복잡도 O(N logN)

방문하지 않은 정점 중 가장 작은 비용의 정점을 찾을 때, 배열을 선형탐색할 때는 O(N2)이었는데

우선순위 큐를 이용해 해당 정점을 Queue에 첫번째 원소에 위치하게 합니다.

※ 우선순위 큐는 내부적으로 Heap 구조

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int stoi(String S) {return Integer.parseInt(S);}
	static final int INF = 1000000000;
	static int N, M, K;
	static List<List<Node>> adList; // 인접 리스트
	static int[] dist; // 최소 거리 비용 테이블
	static boolean[] visited;
	static PriorityQueue<Node> pq;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken()); // 정점의 개수
        M = stoi(st.nextToken()); // 간선의 개수
        K = stoi(br.readLine()); // 출발점
        
        adList = new ArrayList<>();
        // 인덱스를 1부터 하기 위해 임의로 한 개를 넣어둠
        adList.add(new<Node> ArrayList());
        for(int i=1; i<=N; i++) {
            adList.add(new<Node> ArrayList());
        }
        // dist[] INF로 초기화
        dist = new int[N+1];
        Arrays.fill(dist, INF);
        
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
        	int u = stoi(st.nextToken());
        	int v = stoi(st.nextToken());
        	int cost = stoi(st.nextToken());
        	adList.get(u).add(new Node(v, cost));
        }
       
        // 다익스트라 알고리즘
        dijkstra(K);
        
        // 정답출력
        printAnswer();
    }
     
    private static void dijkstra(int start) {
    	pq = new PriorityQueue<>();
    	visited = new boolean[N+1];
    	
    	dist[start] = 0;
    	pq.add(new Node(start, 0));
    	
    	while(!pq.isEmpty()) {
    		Node current =  pq.poll();
    		// 재방문 여부 확인
    		if(visited[current.ID]) continue;
    		visited[current.ID] = true;
    		// 연결된 정점들을 확인 
            for(Node next : adList.get(current.ID)) {
            	// 효율적인 처리를 위해 최소 거리 비용이 갱신되는 경우만 queue에 넣어줍니다.
            	if(dist[next.ID] > dist[current.ID] + next.distance) {
            		// 최소 거리 비용 갱신
                    dist[next.ID] = dist[current.ID] + next.distance;
                    pq.add(new Node(next.ID, dist[next.ID]));
                }
            }
    	}
	}
    
    public static void printAnswer() {
        StringBuilder sb = new StringBuilder();
        for (int i=1; i <= N; i++) {
        	sb.append((dist[i] >= INF ? "INF" : dist[i]));
        	sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

class Node implements Comparable<Node>{
	int ID;
	int distance;
	
	public Node(int ID, int distance) {
		this.ID = ID;
		this.distance = distance;
	}
	
    @Override
    public int compareTo(Node target) {
          // 작은 거리 비용이 먼저 오도록
          return this.distance - target.distance;
    }
}