[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;
​​​​​​​​}
​​​​}
}