[JAVA] 백준 1753 최단경로

 

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

 

 

문제분석

다익스트라 알고리즘을 직접 구현할 때는 그래프를 인접 리스트 형태로 저장하고, 시작 정점에서 각 정점까지의 최소 거리를 배열에 기록하면서 탐색을 진행한다. 먼저 정점의 개수만큼 ArrayList<int[]> 배열을 만들어 각 정점에 연결된 간선 정보를 저장한다. 이때 int[]에는 [도착 정점, 가중치]를 넣어 관리한다. 최소 거리 배열(dij)은 처음에 모두 Integer.MAX_VALUE로 초기화하여 아직 도달하지 못한 상태를 표현하고, 시작 정점의 거리는 0으로 설정한다. 이후 현재 정점과 연결된 모든 간선을 확인하면서 dij[next] = Math.min(dij[next], dij[cur] + weight) 방식으로 거리를 갱신한다. 이 과정은 “현재까지의 최소 거리 + 다음 간선의 가중치”와 기존에 저장된 거리 중 더 작은 값을 선택하는 방식으로 이루어지며, 이를 relaxation(완화) 과정이라고 한다.

 

각 반복에서는 아직 방문하지 않은 정점 중에서 현재까지 계산된 거리 값이 가장 작은 정점을 다음 탐색 대상으로 선택한다. 이때 이미 방문한 정점은 다시 처리하지 않기 위해 visit 배열로 관리한다. 만약 더 이상 도달 가능한 정점이 없다면(즉, 모든 남은 정점의 거리가 무한대라면) 탐색을 종료한다.

코드

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

public class Main {
    static ArrayList<int[]>[] graph; // graph[i]는 i 노드에 연결된 엣지들. [[상대노드, 가중치], ..]
    static int V; // 노드 수
    static int E; // 엣지 수
    static int K; // 시작 정점 번호
    static int[] dij; // 최소 비용 배열, [i]에 j가 저장되어 있다면 i로가는 최소 비용이 j라는 것
    static boolean[] visit; // 방문 여부
    static int count; // 방문 갯수

    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());
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        graph = new ArrayList[V + 1];

        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            // (u,v,w) u에서 v로 w 가중치. 무방향그래프이므로 반대 방향에도 넣어야 함.
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u].add(new int[] { v, w });
        }

        dij = new int[V + 1];
        Arrays.fill(dij, Integer.MAX_VALUE);
        visit = new boolean[V + 1];
        count = 0;

        // K 노드가 시작임
        int node = K;
        dij[node] = 0;
        while (count < V) {
            visit[node] = true;
            int nextNode = 0;

            // node와 연결된 node 및 가중치 확인
            for (int i = 0; i < graph[node].size(); i++) {
                int[] arr = graph[node].get(i);
                int v = arr[0]; // 상대 노드
                int w = arr[1]; // 가중치
                
                // 기존 연결 길이와, 시작->node까지 최소값(dij[node])+node->v까지 거리 합 중 최소값
                dij[v] = Math.min(dij[v], dij[node] + w);
            }

            // i를 아직 방문 안한 경우, 방문 후보 가능한지 확인(가장 작은 값 다음으로 설정함)
            for (int i = 1; i < V + 1; i++) {
                if (!visit[i] && dij[i] != Integer.MAX_VALUE) {
                    if (nextNode == 0 || dij[i] < dij[nextNode]) {
                        nextNode = i;
                    }
                }
            }if (nextNode == 0) break;
            count += 1;
            node = nextNode;
        }
        for (int i = 1; i < dij.length; i++) {
            System.out.println(dij[i] == Integer.MAX_VALUE ? "INF" : dij[i]);
        }

    }
}