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

문제 섫명

 

문제 링크 : https://www.acmicpc.net/problem/18352

 

위의 문제는 전형적인 그래프를 이용한 문제이다.

정점과 정점 사이의 간선의 길이가 모두 1이기 때문에 

가중치가 없는 그래프라고 생각하면 된다.

 

ArrayList <Integer>[]로 그래프를 표현하고 

시작 정점으로부터 BFS로 순회하며 시작 정점과 떨어진 거리가 K인 정점을 찾으면 된다.

시간을 좀 더 줄이기 위해 break에 라벨을 달아 바로 while 문이 종료될 수 있도록 했다.

 

(방문배열을 -1 로 초기화하여 방문여부를 판단해도 괜찮다.)

package boj;

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

public class BOJ18352 {
    static int K;
    static int N;
    static ArrayList<Integer>[] arr;
    static int[] dis; 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N+1];
        for(int i = 0; i < arr.length; i++){
            arr[i] = new ArrayList<>();
        }


        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s].add(e);
        }

        dis = new int[N+1];
        bfs(X);

        List<Integer> answer = new ArrayList<>();

        for(int i = 1; i < dis.length; i++){
            if(dis[i] == K) answer.add(i);
        }

        StringBuilder sb = new StringBuilder();

        if(answer.isEmpty()){
            System.out.println(-1);
        }else{
            for(int num: answer){
                sb.append(num);
                sb.append("\n");
            }
            System.out.println(sb);
        }

    }

    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        visited[start] = true;

        q.add(start);

        out:
        while(!q.isEmpty()){
            int now = q.poll();
            List<Integer> next = arr[now];

            for(int num: next){
                if(!visited[num]){
                    dis[num] = dis[now] + 1;
                    if(dis[num] > K){
                        break out;
                    }
                    visited[num] = true;
                    q.add(num);
                }
            }


        }
    }
}