[코테] 백준 1753번 : 최단경로 (java)

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

알고리즘 분류 : 그래프 이론, 데이크스트라, 최단 경로

❓문제

---

🔅해석

음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제에서는 다익스트라 알고리즘이 사용된다.

다익스트라 알고리즘은 인접리스트 형태로 그래프를 저장하고, Priority Queue를 사용하여 최소 비용의 정점이 먼저 나오도록 한다.

 

// input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

 

 

1. 인접 리스트 생성

ArrayList<Node>[] adjList = new ArrayList[V + 1];

 

2. start로 부터 각 노드까지 최단거리를 담는 dist 배열과 노드를 방문했음을 체크하는 visited 배열을 생성한다.

dist, visited 초기상태

 

3. Priority Queue에 방문 정점을 담아 연결된 정점을 offer한다.

while (!pq.isEmpty()) {
    Node curNode = pq.poll();

    if (visited[curNode.to]) continue;

    visited[curNode.to] = true;

    for (Node nextNode : adjList[curNode.to]) {

        if (dist[nextNode.to] > curNode.w + nextNode.w) {
            dist[nextNode.to] = curNode.w + nextNode.w;
            pq.offer(new Node(nextNode.to, dist[nextNode.to]));
        }
    }
}

 

while 문 내 데이터 변화는 아래와 같다.

 

pq에 new Node(start, 0)를 담아 시작한다.

1에 방문체크를 하고 1과 연결된 2, 3를 탐색하여 dist를 업데이트해준다. 또한, pq에 담아 다음 단계를 진행한다.

 

 

2와 연결된 3, 4를 탐색한다. 이 때 3은 dist[3] < curNode.w (=2) + nextNode.w (=4) 이므로 업데이트 되지 않았다.

 

 

3과 연결된 4를 탐색한다.  dist[4] < curNode.w (=3) + nextNode.w (=6) 이므로 업데이트 되지 않았다.

 

3은 이미 방문체크 된 상태이므로 continue가 된다.

 

4와 연결된 노드가 없으므로 visited, dist에 변화가 없다.

 

4와 연결된 노드가 없으므로 visited, dist에 변화가 없다.

 

이 때 pq가 비게되어 while문이 종료된다.

 

---

⭕정답 코드

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

public class Main {
	
	static int V, E;
	static ArrayList<Node>[] adjList;
	static boolean[] visited;
	static int[] dist;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		
		adjList = new ArrayList[V + 1];
		for(int n=1; n <= V; n++){
            adjList[n] = new ArrayList<>();
        }
		
		int u, v, w;
		for (int e = 1; e <= E; e++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			adjList[u].add(new Node(v, w));
		}
		
		dijkstra(start);
		
		for (int i = 1; i <= V; i++) {
			sb.append(dist[i] >= Integer.MAX_VALUE ? "INF" : dist[i]).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}


	private static void dijkstra(int start) {
		
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		visited = new boolean[V + 1];
		dist = new int[V + 1];
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		
		//visited[start] = true;
		dist[start] = 0;
		pq.offer(new Node(start, 0));
		
		while (!pq.isEmpty()) {
			Node curNode = pq.poll();
			
			if (visited[curNode.to]) continue;
			
			visited[curNode.to] = true;
			
			for (Node nextNode : adjList[curNode.to]) {
				
				if (dist[nextNode.to] > curNode.w + nextNode.w) {
					dist[nextNode.to] = curNode.w + nextNode.w;
					pq.offer(new Node(nextNode.to, dist[nextNode.to]));
				}
			}
		}
	}
}

class Node implements Comparable<Node> {
	int to;
	int w;
	
	public Node(int to, int w) {
		super();
		this.to = to;
		this.w = w;
	}
	
	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.w, o.w);
	}
}

 

---

❗결과