[백준/1754] 최단경로 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1753
• 분류 : 그래프 탐색
• 풀이 시간 : 20분

문제 해설

1. 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하여라
2. 단, 모든 간선의 가중치는 10 이하의 자연수

Solution

풀이 접근 방법

1. 시작점부터 다른 모든 정점까지의 최단 경로
   1. 하나의 시작점 -> 다수의 도착지점까지의 최단 거리 => 다익스트라 / 벨만포드 알고리즘
2. 모든 간선의 가중치는 10 이하의 자연수 -> 음수 없음
   1. => 다익스트라 알고리즘 사용

정답 코드

package com.baekjoon.graph;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_1753 {
  
  static class Node implements Comparable<Node> {
    int idx, cost;

    public Node(int end, int cost) {
      this.idx = end;
      this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
      return Integer.compare(this.cost, o.cost);
    }
  }

  static int V;
  static int INF = 987654321;
  static LinkedList<Node>[] graph;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder answer = new StringBuilder();
    StringTokenizer st = new StringTokenizer(br.readLine());

    V = Integer.valueOf(st.nextToken());
    int E = Integer.valueOf(st.nextToken());
    int start = Integer.valueOf(br.readLine()) - 1;
    graph = new LinkedList[V];

    for (int i = 0; i < V; i++) {
      graph[i] = new LinkedList<Node>();
    }

    while (E-- > 0) {
      st = new StringTokenizer(br.readLine());

      int u = Integer.valueOf(st.nextToken()) - 1;
      int v = Integer.valueOf(st.nextToken()) - 1;
      int w = Integer.valueOf(st.nextToken());

      // 그래프간의 연결 관계 초기화
      // u 노드에서 v노드까지 w의 가중치로 이동할 수 있음
      graph[u].add(new Node(v, w));
    }

    // 시작점 기준으로 모든 정점까지의 최소 거리 구하기
    int[] dist = dijkstra(start);

    for (int cost : dist) {
      answer.append(cost == INF ? "INF" : cost).append("\n");
    }

    bw.write(answer.toString() + "\n");
    bw.flush();
    bw.close();
  }

  static int[] dijkstra(int start) {
    int[] dist = new int[V];
    boolean[] visited = new boolean[V];
    // 가중치를 오른차순 기준으로 낮은 값을 가지는 노드부터 선택
    PriorityQueue<Node> pq = new PriorityQueue<Node>();

    // 모든 노드까지 도착할 수 없다는 의미로 INF로 초기화
    Arrays.fill(dist, INF);
    // 시작점은 0으로 초기화
    dist[start] = 0;
    pq.add(new Node(start, 0));

    while (!pq.isEmpty()) {
      Node current = pq.poll();
      int here = current.idx;

      if (current.cost > dist[current.idx])
        continue;

      // 현재 도착한 노드 기준으로 갈 수 있는 노드들 탐색
      for (Node next : graph[here]) {
        int nIdx = next.idx;
        
        // 이미 방문한 노드면 pass
        if (visited[nIdx])
          continue;

        // 이동할 수 있는 다음 노드로의 최단 거리 > 현재 노드의 최단거리 + 가중치
        if (dist[nIdx] > dist[here] + next.cost) {
          // 다음 노드로의 최단 거리 재설정
          dist[nIdx] = dist[here] + next.cost;
          // 그 다음 노드 방문을 위해 추가
          pq.add(new Node(nIdx, dist[nIdx]));
        }
      }

      // 다 탐색하고 방문했다는 ㅍ시
      visited[here] = true;
    }

    return dist;
  }

}