[필수 문제] 최단거리

1. 문제

그래프와 출발점, 도착점이 주어질 때 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림에서 출발 정점이 0, 도착 정점이 10이라고 할 때, 최단거리는 3이다.

---

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 1,000,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. M+1 번째 줄에 대하여 출발점과 도착점의 정점 번호가 주어진다. 정점의 번호는 0번부터 N-1번까지이다.

출력

출발점에서 도착점까지 이동하기 위한 최단거리를 출력한다.

예제 입력

11 14
0 1
0 2
1 2
1 4
1 5
2 3
3 7
4 7
4 9
4 10
5 6
6 8
6 10
7 8
0 10

예제 출력

3

 

 

 

2. 풀이

최단거리는 다익스트라 알고리즘을 통해 풀 수 있다. 단, 문제에서는 각 간선의 가중치에 대한 정보가 나와있지 않기 때문에 각 가중치를 1로 설정하여 풀면 된다.

 

※ 주의해야할 점은 PriorityQueue를 사용하기 위해 Comaparable을 반드시 implements를 해주어야한다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
    private int node;
    private int weight;

    public Node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    public int getNode() {
        return node;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

class Graph {
    private ArrayList<ArrayList<Node>> graph;

    public Graph(int nodeSize) {
        graph = new ArrayList<>();

        for(int i = 0; i < nodeSize + 1; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public ArrayList<Node> getNode(int n) {
        return graph.get(n);
    }

    public void put(int n, int m, int weight) {
        graph.get(n).add(new Node(m, weight));
        graph.get(m).add(new Node(n, weight));
    }
}

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int m;

    private static Graph graph;
    private static int[] dist;
    private static boolean[] isVisited;

    private final static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new Graph(n);
        dist = new int[n + 1];
        isVisited = new boolean[n + 1];

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.put(a, b, 1);
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        bw.write(dijkstra(start, end) + "");

        br.close();
        bw.flush();
        bw.close();
    }

    private static int dijkstra(int s, int e) {
        Arrays.fill(dist, INF);
        Arrays.fill(isVisited, false);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(s, 0));
        dist[s] = 0;

        while(!pq.isEmpty()) {
            Node curPoint = pq.poll(); // 현재 노드
            int curNode = curPoint.getNode();
            int curWeight = curPoint.getWeight();

            if(!isVisited[curNode]) {
                isVisited[curNode] = true;

                for(int i = 0; i < graph.getNode(curNode).size(); i++) {
                    int nextNode = graph.getNode(curNode).get(i).getNode();
                    int nextWeight = graph.getNode(curNode).get(i).getWeight();
                    
                    // 현재의 노드에 담긴 거리값이 다음 가중치를 더한 값보다 클 경우 최단거리가 아니므로 더한 값을 넣어준다.
                    if(!isVisited[nextNode] && dist[nextNode] > curWeight + nextWeight) {
                        dist[nextNode] = curWeight + nextWeight;
                        pq.add(new Node(nextNode, dist[nextNode]));
                    }
                }
            }
        }
        return dist[e];
    }

}