[Baekjoon] 18352번 특정 거리의 도시 찾기 (Java) 문제 풀이 [Sliver 2]

문제

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

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

 

어떻게 풀 것인가?

특정 최단경로의 거리를 묻는 문제이다. 다익스트라를 이용하여 문제를 풀 수도 있지만, 나는 간단하게 BFS로 문제를 해결하였다.

 

최단경로를 묻는 것이 아닌 특정 최단경로의 거리를 묻는 것이기 때문에 그래프적 접근이 훨씬 좋다고 생각하였다.

 

풀면서 놓쳤던점

X

 

이 문제를 통해 얻어갈 것

BFS의 사용법

 

내 코드 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();

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

        boolean[] chk = new boolean[n + 1]; // 방문 기록
        int[] distance = new int[n + 1]; // 이동 거리 배열

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }

        ArrayList<Integer> result = new ArrayList<>(); // 결과를 담을 리스트

        // BFS 함수
        bfs(graph, chk, distance, x, k, result);

        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(result);
            for (int i : result) {
                System.out.println(i);
            }
        }
    }

    public static void bfs(ArrayList<ArrayList<Integer>> graph, boolean[] chk, int[] distance, int start, int k, ArrayList<Integer> result) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        chk[start] = true;

        while (!q.isEmpty()) {
            int now = q.poll();
            for (int i : graph.get(now)) {
                if (!chk[i]) {
                    chk[i] = true;
                    distance[i] = distance[now] + 1;
                    q.add(i);
                    if (distance[i] == k) {
                        result.add(i);
                    }
                }
            }
        }
    }
}

 

참고

X