[백준 JAVA] 18352. 특정 거리의 도시 찾기

문제 링크

---

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

 

접근 방법

---

모든 도로의 거리는 1로 동일하므로 다익스트라가 아닌 bfs로 접근합니다.

소스 코드

---

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int city, road, d, s;
        StringTokenizer st = new StringTokenizer(br.readLine());

        city = Integer.parseInt(st.nextToken());
        road = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        int[] dist = new int[city  + 1];
        boolean[] visited = new boolean[city + 1];
        List<Integer>[] graph = new ArrayList[city + 1];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE;
        }

        int a, b;
        for (int i = 0; i < road; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
        }

        ArrayDeque<Integer> q = new ArrayDeque<>();
        dist[s] = 0;
        q.addFirst(s);
        visited[s] = true;

        while (!q.isEmpty()) {
            int cur = q.removeLast();

            visited[cur] = true;
            for (int next : graph[cur]) {
                if (!visited[next]) {
                    dist[next] = dist[cur] + 1;
                    q.addFirst(next);
                    visited[next] = true;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= city; i++) {
            if (dist[i] == d) {
                sb.append(i).append('\n');
            }
        }

        if (sb.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(sb);
        }
    }
}

 

코드 설명

---

방향이 있는 그래프이므로 인접리스트로 구현합니다.

모든 도시를 방문한 후, 최단거리가  k와 같은 도시들을 뽑아냅니다.