[JAVA] 백준 그대, 그머가 되어

BFS 아니고, 다익스트라 알고리즘 문제이다. 

 

두 알고리즘 용도가 헷갈렸는데, 아래 정리해보았다.

BFS탐색: 시작점으로부터 어떤 정점까지 너비우선적으로 탐색한다. 최단경로를 구할 때 사용할 수도 있다.
다익스트라: 시작점으로부터 나머지 모든 정점까지의 최단경로를 구할 때 사용

 

다익스트라 위 문제에서는 아래 코드가 키 포인트다.

 
 static final int INF = 1000000000;
 static List<Integer>[] list = new ArrayList[1001];//리스트 배열
 static int[] dist = new int[1001];
    
 private static void dijkstra(int start) {

        Queue<Node> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node n = pq.poll();
            int cur = n.end;
            int d = n.dist;

            if (dist[cur] < d) continue;

            for (int next : list[cur]) {//모든 연결노드로 갱신
                if (dist[next] > d + 1) {//"현재 거리 > 한칸 전진한값" 일때 갱신
                    dist[next] = d + 1;
                    pq.add(new Node(next, d + 1));
                }
            }
        }
    }

 

아래는 다익스트라로 각각의 정점에 대하여 최단경로를 갱신하면 되는 문제이므로 아래 코드를 남기겠다.

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

public class Main {
    static int a, b, N, M;
    static final int INF = 1000000000;
    static List<Integer>[] list = new ArrayList[1001];
    static int[] dist = new int[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            dist[i] = INF;
        }


        for (int i = 0; i <= M - 1; i++) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());

            list[h].add(tg);
            list[tg].add(h);
        }

        dijkstra(a);

        System.out.println(dist[b] == INF ? -1 : dist[b]);
    }

    private static void dijkstra(int start) {

        Queue<Node> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node n = pq.poll();
            int cur = n.end;
            int d = n.dist;

            if (dist[cur] < d) continue;

            for (int next : list[cur]) {
                if (dist[next] > d + 1) {
                    dist[next] = d + 1;
                    pq.add(new Node(next, d + 1));
                }
            }
        }
    }

    static class Node {
        int end, dist;

        public Node(int end, int dist) {
            this.end = end;
            this.dist = dist;
        }
    }
}