[JAVA ] 백준 18352 그래프

 

 

 

 

 

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

문제

단방향 도로가 있는 도시들이 있고 출발지가 주어졌을 때 거리가 K인 도시를 모두 출력하시오.

풀이

출발지로부터 깊이를 구하는 문제라고 생각했고 BFS를 통해 문제를 풀었습니다.

입력

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            A[x].add(y);
        }

방향이 있는 도로였기 때문에 방향에 맞춰 간선을 표현하였습니다.

📌 BFS

    public static void BFS(int start){
        Queue<Integer> q = new LinkedList<>();

        depth[start] = 0;
        q.add(start);
        V[start] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    q.add(x);
                    V[x] = true;
                    depth[x] = depth[now] + 1;
                }
            }
            if(depth[now] > K) break;
        }

    }

now값의 depth를 다음 노드에 추가하여 depth들을 만들었습니다.

속도를 더 빠르게 하기 위해서 현재 노드의 depth값이 K보다 커지면 종료했습니다.

📌 출력

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<N; i++){
            if(depth[i] == K) sb.append(i).append("\n");
        }

        System.out.println(sb.length() < 1 ? -1 : sb);

StringBuilder를 통해 출력하였고 sb의 길이가 1보다 작다면 주어진 거리의 노드가 없다는 것을 의미하므로 -1을 출력하였습니다.

📌 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static ArrayList<Integer>[] A;
    static boolean[] V;
    static int[] depth;
    static int K;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        V = new boolean[N];
        A = new ArrayList[N];
        depth = new int[N];
        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            A[x].add(y);
        }

        BFS(X);
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<N; i++){
            if(depth[i] == K) sb.append(i).append("\n");
        }

        System.out.println(sb.length() < 1 ? -1 : sb);
    }

    public static void BFS(int start){
        Queue<Integer> q = new LinkedList<>();

        depth[start] = 0;
        q.add(start);
        V[start] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    q.add(x);
                    V[x] = true;
                    depth[x] = depth[now] + 1;
                }
            }
            if(depth[now] > K) break;
        }

    }
}

결과