[JAVA] 백준 1753번 - 최단경로

<문제>

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

방향그래프의 주어진 시작점에서 다른 모든 정점으로의 최단경로를 구하는 프로그램 작성(모든 간선의 가중치는 10 이하의 자연수)

<입력>

#1: 정점 V개, 간선 E개, 모든 정점에는 1부터 V까지 번호
#2: 시작 정점 번호 K
#3~: E개 줄에 각 간선을 나타내는 3개의 정수(u, v, w) - u에서 v로 가는 가중치 w인 간선 존재(u,v는 서로 다르며 w는 10 이하의 자연수)

• 서로 다른 두 정점 사이에 여러개의 간선이 존재할 수도 있음!

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

<출력>

• V개의 줄에 거쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력(시작점 자신은 0 출력, 경로가 존재하지 않을 시 INF출력)

0
2
3
7
INF

<풀이>

• 인접리스트 구현 + 우선순위 큐 이용
• 총 4개의 배열 및 리스트 이용함
  • visited: 해당 정점을 방문하였는지 저장 boolean타입
  • list: 인덱스(시작정점), 안의 ArrayList는 Node타입(end, weight)
  • result: 최단 거리만을 저장하는 배열
  • pq(우선순위 큐): result에 저장하기 위해 List를 가지고 최단 거리를 계산하게 해주는 중개자

1. list- 새로운 ArrayList 삽입, result-Integer.MAX_VALUE; //int형 변수가 가질 수 있는 최대값(2,147,483,647) 초기화
2. list에 Node타입 저장
3. 우선순위 큐 pq생성(최소힙) → result[K] = 0 삽입 (K:시작정점) → pq에 Node(K,0) 추가
4. pq가 비어있을 때 까지 반복
   • pq에서 꺼내 현재 Node확인 후 방문(visited[])하지 않았다면 true(방문)으로 변경 / 방문 시 무시
   • list[end]의 사이즈만큼 반복
     • end의 값을 가져와 Node타입 next로 저장
     • if - 방문X && (현재 가중치+다음 가중치)<result[] ⇒ 가중치들의 합을 result[]에 저장, pq에 다음 노드 정보 저장
5. 반복이 끝나면 출력 - result 에서
   • 만약 result에 Integer.MAX_VALUE 값이라면 최단경로가 없다는 것이므로 INF출력
   • 값이 있다면 출력

=> 이 풀이대로 아래 코드를 작성하였다. 위의 풀이 순서대로 작성한 것이라 이해가 잘될 것이다.

<전체코드>

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    int end, weight;
    public Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node node) {
        return weight - node.weight;
    }
}
public class Main {
    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()); // 정점 시작 번호
        boolean[] visited = new boolean[V+1]; //방문 처리
        int[] result = new int[V+1]; //최단 경로 값 저장
        List<Node>[] list = new List[V+1]; //연결 정보 저장

        for(int i=1; i<=V; i++) { //list, result 초기화
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); //출발
            int v = Integer.parseInt(st.nextToken()); //도착
            int w = Integer.parseInt(st.nextToken()); //가중치

            list[u].add(new Node(v,w));
        }

        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)->n1.weight-n2.weight);
        result[K] = 0;
        pq.add(new Node(K,0));

        while(!pq.isEmpty()) {
            Node current = pq.poll();
            if(!visited[current.end])
                visited[current.end] = true;
            for(int i=0; i<list[current.end].size(); i++) {
                Node next = list[current.end].get(i);
                if(!visited[next.end] && current.weight+next.weight < result[next.end]) {
                    result[next.end] = current.weight+next.weight;
                    pq.add(new Node(next.end, result[next.end]));
                }
            }
        }
        for(int i=1; i<=V; i++) {
            if(result[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else
                System.out.println(result[i]);
        }
    }
}