[Day10]JAVA- 백준 특정 거리의 도시 찾기 (18352번)

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

 

 

백준 18352번 문제를 풀기위해서는 BFS 에 대해서 알아야 한다.

 

BFS 에 대해서 잘 알고 있으면 어려운 문제는 아니지만 , 함정이 있다! 문제를 꼼꼼히 읽어야 한다.

BFS,DFS 문제를 많이 풀다보면은 어느정도 문제를 읽다보면 어떠한 알고리즘을 사용해야겠다 감이 잡힌다. 

그래서 대강 문제를 읽보 바로 풀어버리는 실수를 하게 되는것이다.

 

이 문제에서 포인트는 단방향의 도로인것과 , 도시의 번호를 오름차순으로 출력하는 것이다.

보통을 노드 사이는 양방향인 경우가 많아 아래와 같이 선언해 주는 경우가 많다. 

graph.get(u).add(v);
grpah.get(v).add(u);

 

단방향은 한방향으로만 선언해 줘야 한다!

graph.get(u).add(v);

 

 

 

문제는 간단하다 Queue 를 사용하여 방문한 도로를 넣고 빼면서 result 배열에 방문한 거리를 이전의 도시거리 값 +1 로 구하는 것이다. 

 

 

*최종코드

// 18352번
import java.util.*;
import java.io.*;
public class Main{
    static int N; //도시의 개수
    static int M; //도로의 개수
    static int K; //거리 정보
    static int X; //출발도시 번호 
    static boolean[] visited;
    static int[] result;

    static ArrayList<ArrayList<Integer>> graph= new ArrayList<>();
    static ArrayList<Integer> answer = new ArrayList<>();

   public static void main(String[] args) throws IOException
   {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        //노드 초기화
        for(int i=0;i<=N;i++)
        {
            graph.add(new ArrayList<>());
        }

        visited = new boolean[N+1];
        result = new int[N+1];
                
        //도로 초기화
        for(int i=0;i<M;i++)
        {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);  //단방향
        }

        BFS(X);

        if(answer.isEmpty())
            System.out.println("-1");
        else
        {
            //오름차순
            Collections.sort(answer);
            for(int i=0;i<answer.size();i++)
            {            
                System.out.println(answer.get(i));
            }
        }
    }

   public static void  BFS(int v)
   {
        Queue<Integer> que = new LinkedList<>();
        que.add(v);
        visited[v] = true;

        while(!que.isEmpty())
        {
            int c = que.poll();

            for(int g : graph.get(c))
            {
                if(!visited[g])
                {             
                    que.add(g);
                    visited[g] = true;
                    result[g] = result[c]+1;

                    if(result[g] == K)
                    {
                        answer.add(g);
                    }

                }
            }
        }
    }
}