[18352] 특정 거리의 도시 찾기

✔ 특정 거리의 도시 찾기

[백준 18352]

문제 분석하기

모든 도로의 거리가 1이므로 가중치가 없는 인접 리스트로 그래프를 표현한 후, BFS 탐색을 수행

손으로 풀어보기

1. 인접 리스트로 도시와 도로 데이터의 그래프를 구현
2. BFS 탐색 알고리즘으로 탐색을 수행하면서 각 도시로 가는 최단 거릿값을 방문 배열에 저장
3. 탐색 종료 후 방문 배열에 값이 K와 같은 도시의 번호를 출력

슈도코드 작성하기

N(노드 개수) M(엣지 개수) K(목표 거리) X(시작점)
answer(정답 리스트)
A(그래프 데이터 저장 인접 리스트) visited(방문 거리 저장 배열)
for(N의 개수만큼 반복하기) {
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(M의 개수만큼 반복하기) {
    A 인접 리스트에 그래프 데이터 저장하기
}
visited 배열 초기화하기
BFS(X) 실행하기
for(N의 개수만큼 반복하기) {
    방문 거리가 K인 노드의 숫자를 정답 배열에 더하기
}
정답 배열 오름차순 정렬해 출력하기

BFS {
    큐 자료구조에 출발 노드 더하기(add 연산)
    visited 배열에 현재 노드 방문 기록하기
    while(큐가 빌 때까지) {
        큐에서 노드 데이터를 가져오기(poll 연산)
        현재 노드의 연결 노드 중 방문하지 않은 노드로
        이전 노드의 방문 노드 거리 + 1
        큐에 데이터 삽입(add 연산)하고 visited 배열에 방문 거리 기록하기
    }
}

코드 구현하기

/**
 * 18352) 특정_거리의_도시_찾기
 */
public class D046_18352 {
    static int visited[];
    static ArrayList<Integer>[] A;
    static int N, M, K, X;
    static List<Integer> answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(노드 개수)
        N = sc.nextInt();
        // M(엣지 개수)
        M = sc.nextInt();
        // K(목표 거리)
        K = sc.nextInt();
        // X(시작점)
        X = sc.nextInt();
        // A(그래프 데이터 저장 인접 리스트)
        A = new ArrayList[N + 1];
        // answer(정답 리스트)
        answer = new ArrayList<>();
        // A 인접 리스트의 각 ArrayList 초기화하기
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<Integer>();
        }
        // A 인접 리스트에 그래프 데이터 저장하기
        for (int i = 0; i < M; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();
            A[S].add(E);
        }
        // visited(방문 거리 저장 배열)
        visited = new int[N + 1];
        // visited 배열 초기화하기
        for (int i = 0; i <= N; i++) {
            visited[i] = -1;
        }
        // BFS(X) 실행하기
        BFS(X);
        // 방문 거리가 K인 노드의 숫자를 정답 배열에 더하기
        for (int i = 0; i <= N; i++) {
            if (visited[i] == K) {
                answer.add(i);
            }
        }
        // 정답 배열 오름차순 정렬해 출력하기
        if (answer.isEmpty()) {
            System.out.println("-1");
        } else {
            Collections.sort(answer);
            for (int temp : answer) {
                System.out.println(temp);
            }
        }
    }

    // BFS 구현하기
    public static void BFS(int Node) {
        // 큐 자료구조에 출발 노드 더하기
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        // visited 배열에 현재 노드 방문 기록하기
        visited[Node]++;
        while (!queue.isEmpty()) {
            // 큐에서 노드 데이터를 가져오기
            int now = queue.poll();
            // 현재 노드의 연결 노드 중 방문하지 않은 노드로
            for (int i : A[now]) {
                if (visited[i] == -1) {
                    // visited 배열에 방문 거리 기록하기 (이전 노드의 방문 노드 거리 + 1)
                    visited[i] = visited[now] + 1;
                    // 큐에 데이터 삽입
                    queue.add(i);
                }
            }
        }
    }
}