[JAVA] 다익스트라 알고리즘

1. 특정 거리의 도시 찾기

bfs로 풀었고, 거리가 1이라서 간단하게 풀렸음

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

class Main {
    // 입력값: 도시 개수, 간선 개수, 최단 거리, 출발 도시 번호
    // 모든 도로 거리는 1
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); 
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken())-1;

        List<List<Integer>> graph = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < m; i++) {
            StringTokenizer stt = new StringTokenizer(br.readLine()); 
            int a = Integer.parseInt(stt.nextToken())-1;
            int b = Integer.parseInt(stt.nextToken())-1;

            graph.get(a).add(b);
        }

        int[] dist = bfs(graph,n,x,k);
        int count = 0;
        for(int i = 0; i < n; i++) {
            if( dist[i] == k) {
                System.out.println(i+1);
                count++;
            }
            
        }
        if(count == 0) System.out.println(-1);

    }
    static int[] bfs(List<List<Integer>> graph, int n, int start, int k){
            int[] dist = new int[n+1];
            Arrays.fill(dist,-1);

            Queue<Integer> q = new LinkedList<>();
            q.offer(start);
            // 방문 표시
            dist[start] = 0;
            while(!q.isEmpty()){
                int now = q.poll();
                for(int next : graph.get(now)){
                    // 방문 안했다면 거리 +1 , 다음노드 큐에 삽입
                    if(dist[next] == -1){
                        dist[next] = dist[now] + 1;
                        q.offer(next);
                    }
                }
            }
        return dist;
    }
}