[백준 - 18352] 특정 거리의 도시 찾기 .java

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

 

 

문제 분석

• 모든 도로의 거리가 1 -> 가중치가 없는 인접 리스트로!
• 최단 거리 -> BFS 탐색

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;

public class Main {
    static int[] visited;//방문거리
    static ArrayList<Integer>[] list;
    static List<Integer> answer;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //노드 수
        int m = sc.nextInt(); //에지 수
        int k = sc.nextInt(); //목표거리
        int x = sc.nextInt(); //시작점
        list = new ArrayList[n+1]; //도시 번호 시작 1부터
        answer = new ArrayList<>();

        //n개로 초기화
        for(int i=1;i<=n;i++){
            list[i] = new ArrayList<>();
        }

        //에지 정보
        for(int i=0;i<m;i++){
            int s = sc.nextInt();
            int e = sc.nextInt();
            list[s].add(e);
        }

        visited = new int[n+1];//방문배열 초기화
        for(int i=1;i<=n;i++){
            visited[i] = -1;//방문하지 않은 노드를 -1로 초기화
        }
        BFS(x); //시작점부터 BFS

        //거리가 k인 도시 번호를 정답에 추가
        for(int i=1;i<=n;i++){
            if(visited[i] == k){
                answer.add(i);
            }
        }

        //구한 결과가 비어있으면
        if(answer.isEmpty()){
            System.out.println("-1");
        } else {
            //도시 번호 오름차순
            Collections.sort(answer);
            for(int i : answer){
                System.out.println(i);
            }
        }
    }
    static void BFS(int node){
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(node);//시작 노드를 큐에 추가
        visited[node]++;
        while(!q.isEmpty()){
            int now = q.poll();//큐에서 현재 노드를 꺼냄
            //현재 노드와 연결된 모든 노드에 대해
            for(int i : list[now]){
                if(visited[i]==-1){//방문 안한 노드면
                    visited[i] = visited[now]+1;//현재 노드의 거리 + 1을 저장
                    q.add(i);
                }
            }
        }
    }

}