[BOJ 18352] 특정 거리의 도시 찾기 (Java, BFS)

---

문제 링크 

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

18352번: 특정 거리의 도시 찾기

---

풀이 

- BFS 활용하여 X 부터 다른 노드까지의 거리 배열 구한 후 K에 해당하는 거리값을 가지는 노드 오름차순으로 풀이 

- 간선의 비용이 1이기 때문에 최단 거리가 아닌 BFS 만으로도 풀이 가능 

 

*실수

1) 거리 배열(DIST)를 최대값으로 초기화 하지 않은 것

Arrays.fill(DIST, Integer.MAX_VALUE)

2) 연결된 간선 조회시 이전에 구한 간선으로 이동하는 비용과 현재 간선의 비용을 비교하지 않은 것 (풀이가 최단거리와 비슷)

 

 

초기 DIST(거리 배열) 선언 후 구함

1	2	3	4
0	21억	21억	21억

 

---

제출 

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N, M, K, X;

    static int[] DIST;

    static List<Integer>[] adj;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 도시의 개수 (=정점)
        M = Integer.parseInt(st.nextToken()); // 도로의 개수 (=간선)
        K = Integer.parseInt(st.nextToken()); // 거리 정보
        X = Integer.parseInt(st.nextToken()); // 시작 번호

        DIST = new int[N + 1];

        adj =  new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        // 단반향 그래프
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            adj[from].add(to);
        }

        for(int i = 1; i <= N; i++) {
            Collections.sort(adj[i]);
        }

        br.close();
    }

    static void bfs(int start) {
        Arrays.fill(DIST, Integer.MAX_VALUE);
        
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        DIST[start] = 0;

        while(!que.isEmpty()) {
            int x = que.poll();

            for(int y : adj[x]) {
                if(DIST[y] <= DIST[x] + 1) continue;

                DIST[y] = DIST[x] + 1;
                que.add(y);
            }
        }
    }


    static void pro() {
        bfs(X);
        boolean find = false;
        for(int i = 1; i <= N; i++) {
            if(DIST[i] == K) {
                find = true;
                sb.append(i).append("\n");
            }
        }

        if(!find) System.out.println(-1);
        else System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}