[BOJ] 4485. 녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485

접근 방법

(0,0) → (N-1,N-1)로 이동을 할 때 가장 적은 비용으로 가야함.

다익스트라 알고리즘

https://dev-room.tistory.com/18

Need Know

1. 다익스트라 알고리즘

전체 코드 ( Java )

import javafx.scene.Node;

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int[] dist;
    static ArrayList<Integer>[] map;
    static PriorityQueue<MyNode> pq;
    public static void main(String[] args) throws IOException {
        set();

        solve();
    }
    static void set() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dist = new int[N+1];
        for(int i=2; i<N+1; i++) dist[i] = Integer.MAX_VALUE;
        map = new ArrayList[N+1];
        for(int i=1; i<N+1; i++){
            map[i] = new ArrayList<>();
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[a].add(b);
            map[b].add(a);
        }
        pq = new PriorityQueue<>();
        pq.add(new MyNode(1,0));

    }
    static void solve(){
        while(!pq.isEmpty()){
            MyNode now = pq.poll();
            int index = now.index;
            int distance = now.distance;

            if(dist[index] < distance) continue;

            for(int i=0; i< map[index].size(); i++){
                int next = map[index].get(i);
                int nextDist = distance + 1;

                if(dist[next] <= nextDist) continue;

                dist[next] = nextDist;
                pq.add(new MyNode(next,nextDist));
            }
        }
        int num = 1;
        int distance = 0;
        int ans = 1;
        for(int i=2; i<N+1; i++){
            if(distance < dist[i]){
                distance = dist[i];
                num = i;
                ans = 1;
            }else if(distance == dist[i]){
                ans++;
            }
        }
        System.out.println(num +" "+distance +" "+ ans);
    }
}
class MyNode implements Comparable<MyNode>{
    int index;
    int distance;
    public MyNode(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }
    @Override
    public int compareTo(MyNode o) {
        return distance-o.distance;
    }
}