99클럽 코테 스터디 31일차 TIL [다익스트라]

- 오늘의 학습 키워드 : 다익스트라

[문제 이름 : 택배 배송 (백준, G5)]
문제 url : https://www.acmicpc.net/problem/5972

내가 작성한 코드는 아래와 같다.

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<Node>[] A;
    static final int INF = Integer.MAX_VALUE;
    static int[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        A = new ArrayList[n+1];
        dist = new int[n+1];
        for(int i=1; i<=n; i++) {
            A[i] = new ArrayList<>();
            dist[i] = INF;
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            A[start].add(new Node(end, value));
            A[end].add(new Node(start, value));
        }

        dijkstra(1);
        System.out.println(dist[n]);
    }
    
    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            int curNode = cur.end;
            int curValue = cur.value;
            
            if(curValue > dist[curNode]) continue;
            
            for(Node next : A[curNode]) {
                int nextNode = next.end;
                int nextValue = curValue + next.value;
                
                if(nextValue < dist[nextNode]) {
                    dist[nextNode] = nextValue;
                    pq.add(new Node(nextNode, nextValue));
                }
            }
        }
    }

    static class Node implements Comparable<Node>{
        int end;
        int value;

        Node(int end, int value) {
            this.end = end;
            this.value = value;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.value - n.value;
        }
    }
}

풀이 과정(풀이 시간 : 15분)

다익스트라 문제였고, 함정이 없어서 빠르게 풀이할 수 있었다.

 

1. ArrayList[Node]<> A;를 선언하여, 시작점, 도착점,여물 값을 저장한다. 이때, 양방향 이동이 가능하므로 입력값 저장 시 

A[start].add(), A[end].add()로 두 번 저장한다.

2. dijkstra 알고리즘을 사용해서, 현재 pq에서 빼온 현재 노드와 현재 여물값을 저장한다. 해당 점과 이어져 있는 정점들 중에서, 현재 value에서 최소값으로 이동할 수 있는 nextValue값을 구한다면, dist[] 배열을 갱신해준 뒤에 pq값을 추가해준다.

3. N에 해당하는 최소 여물의 양을 구해야 하므로, dist[n]값을 출력해주면 된다.


내일은 다음주 화요일에 있을 기업 면접을 준비할 예정이다.