15.특정 거리의 도시 찾기

📍 문제 설명

 

💡 접근

4개의 숫자중에 2개를 뽑는 순열문제임

방문안한 노드에 대해서만 거리 기록하여 풀이

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt(); //도시 갯수
        int m = kb.nextInt(); //도로 갯수
        int k = kb.nextInt(); //거리 정보
        int x = kb.nextInt(); //출발 도시 번호

        ch = new int[n+1]; //도시 방문 체크 배열(1번 부터)
        dis = new int[n+1]; //도로의 거리 기록 배열(1번 부터)


        graph = new ArrayList<ArrayList<Integer>>();
        //0번 정점은 사용안하지만 n번 정점에서 뻗을 수도 있으므로 이렇게 선언해야함
        for(int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        //거리 정보 넣기
        for(int i = 0; i < m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);
        }

        //출발 정점에서 시작
        BFS(x);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < dis.length; i++) {
            if(dis[i] == k) list.add(i);
        }
        if(list.size() == 0) System.out.println(-1);
        else {
            Collections.sort(list);
            for(int lis : list) System.out.println(lis);
        }
    }

    private static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        //해당 정점을 일단 방문처리 해놓는다.
        ch[v] = 1;
        //자기 자신에게 가는거리는 0임
        dis[v] = 0;
        //해당 정점 큐에 삽입
        queue.offer(v);
        while (!queue.isEmpty()) {
            //현재 정점꺼내서
            int cv = queue.poll();
            //연결된 정점 확인하기
            for(int nv : graph.get(cv)) {
                //방문 안한곳만 방문해서 방문처리 + 큐삽입 + 거리기록
                if(ch[nv] == 0) {
                    ch[nv] = 1;
                    queue.offer(nv);
                    dis[nv] = dis[cv] + 1;
                }
            }
        }

    }
}