[백준]1240: 노드사이의 거리 - JAVA

[백준]1240: 노드사이의 거리

www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

풀이

두 노드 사이의 최단 경로를 반환하는 문제였다. 다양한 방법이 있겠지만 나는 다익스트라 알고리즘을 사용하여 풀었다. 노드와 간선 가중치의 정보를 입력 받은 후 M개의 개수 만큼 다익스트라 알고리즘을 돌려 M개의 거리를 출력하였다.

 

다익스트라 알고리즘은 우선순위 큐(최소힙)와 dist배열, visited배열을 사용하여 구현해 주었다. 기본적인 다익스트라 알고리즘을 구현할 수 있는지 묻는 수준의 문제였고 어렵지 않게 풀었다.

 

코드

import java.util.*;
 
public class Main {    
 
    static int n, m;
    static ArrayList<Node>[] list;
    static int[] dist;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < n - 1; i++) {
            int s = scan.nextInt();
            int d = scan.nextInt();
            int v = scan.nextInt();
            list[s].add(new Node(d, v));
            list[d].add(new Node(s, v));
        }
        
        for(int i = 0; i < m; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            dist = new int[n + 1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            visited = new boolean[n + 1];
            dijkstra(start, end);
            System.out.println(dist[end]);
        }
    }    
    
    public static void dijkstra(int s, int e) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        dist[s] = 0;
        q.offer(new Node(s, 0));
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(visited[current.n] == false) visited[current.n] = true;
            else continue;
            
            for(int i = 0; i < list[current.n].size(); i++) {
                Node next = list[current.n].get(i);
                if(dist[next.n] > dist[current.n] + next.v) {
                    dist[next.n] = dist[current.n] + next.v;
                    q.offer(new Node(next.n, dist[next.n]));
                }
            }
        }
    }
    
    public static class Node implements Comparable<Node> {
        int n;
        int v;
        
        public Node(int n, int v) {
            this.n = n;
            this.v = v;
        }
        
        @Override
        public int compareTo(Node node) {
            return this.v - node.v;
        }
    }
}