[ Baekjoon ] 1753번 - 최단경로

1753번: 최단경로

 

풀이 방법

다익스트라 알고리즘 관련된 문제를 이번에 처음 접해보았다. 푸는데 해당 알고리즘을 코드로 구현하는데는 어렵지 않았다.

하지만, 1. 메모리 초과로 인해 인접리스트와 1차원 배열로 변경 2. 시간 초과로 인해 우선순위 큐로 변경 3. INF의 범위

이렇게 고려해야할 요소들이 많아 풀었던 문제를 수정하는데에 정말 많은 시간이 소요되었다. 중간에 정말 때려치우고 싶었다. 아예 모르는 문제보다 아는데 계속 빙빙 돌아서 가는 느낌의 문제를 별로 안좋아하는 것 같다. 모르는 문제는 신기하기라도 하는데... 계속 수정해도 오류가 계속 있는,,, 이 답답함..🤦‍♀️🤦‍♀️

 

구현 코드

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 Q_1753 {
    static int V, E, K;
    static PriorityQueue<Graph> priorityQueue = new PriorityQueue<>();
    static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        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()); // 시작 노드

        ArrayList<ArrayList<Graph>> array = new ArrayList<ArrayList<Graph>>();
        for (int i = 0; i <= V; i++) {
            array.add(new ArrayList<Graph>());
        }
        
        int start, end, weight;
        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
            array.get(start).add(new Graph(end, weight));
        }
        
        int[] distance = new int[V+1];
        int[] visited = new int[V+1];
        Arrays.fill(distance, INF); // distance를 INF로 채우기
        priorityQueue.offer(new Graph(K, 0));
        distance[K] = 0;
        while(!priorityQueue.isEmpty()) {
            // STEP 1: 집합에 들어있는 노드로부터 아직 방문하지 않은 노드까지의 거리를 구한다.
            int w = priorityQueue.poll().end;
            if (visited[w] == 1)
                continue;
            
            visited[w] = 1;
            
            // dijkstra 알고리즘
            for (Graph g : array.get(w)) {
                if (distance[g.end] > distance[w] + g.weight) { 
                    distance[g.end] = distance[w] + g.weight;
                    // STEP 2: 최소값을 갖는 노드를 찾아 priorityQueue에 넣는다.
                    priorityQueue.add(new Graph(g.end, distance[g.end]));
                }
            }
        }
        
        // 출력
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= V; i++) {
            if (distance[i] != INF)
                sb.append(distance[i]+"\n");
            else 
                sb.append("INF\n");
        }
        
        System.out.println(sb);
    }
    
    // array 배열에 시작노드부터 end노드까지의 weight를 표현하기 위함
    static class Graph implements Comparable<Graph> {
        int end;    
        int weight;
        
        Graph(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
        
        @Override
        public int compareTo(Graph g) {
            return this.weight - g.weight;
        }
    }
}