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

백준 18352번 문제 - 특정 거리의 도시 찾기

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

---

문제 분석

 

 

•  도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X를 입력 받고, M개의 도로가 어떻게 이뤄져있는지 입력받는다.
• 이를 토대로, X에서 출발했을 때 어떤 도시까지 갈 때 최단 거리가 K번인 도시들을 출력해라 (오름차순으로)
  • 만약 그런 도시가 없을 경우, -1 출력

---

 

해결 키 포인트

• BFS(너비 우선 탐색) 개념 파악
• 오름차순 출력을 위해, Arrays.sort 이용
  • 현재 BFS로 확인했을 때, 깊이 정도가 K와 동일할 경우 queue에 남은 값을 List에 담는다
  • Arrays.sort로 오름차순 정렬한다
  • 이때, PriorityQueue를 사용하면 안되는 이유는 큐 순서가 뒤죽박죽이 되서 너비 탐색이 제대로 일어나지 않기 때문이다

 

---

너비 우선 탐색(BFS)

 

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

너비 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 선입 선출 특성을 가짐 ( 큐 사용 )

 

알고리즘

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

 

Do It! 알고리즘 코딩 테스트

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입 (이를 모든 정점에 다한다)

 

Do It! 알고리즘 코딩 테스트

만약 큐에 노드가 없으면, 방문하지 않은 정점을 알아내, 큐에 삽입하고 다시 2번 단계를 반복한다.

---

 

---

코드

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

public class Main {
    static BufferedWriter bw;
    static ArrayList<Integer> [] lists;
    static boolean [] isChecked;
    static int N,K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력
        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());

        // N개의 도시 초기화
        lists = new ArrayList [N];
        isChecked = new boolean[N];

        for(int i=0;i<N;i++) {
            lists[i] = new ArrayList<>();
        }

        // M개의 도로 입력
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            lists[start-1].add(end-1);
        }

        // bfs 실행
        bfs(X-1);

        bw.flush();
        bw.close();
    }

    public static void bfs(int x) throws IOException {
        Queue<Integer> queue = new LinkedList<>();

        // 시작 인덱스 초기화
        queue.add(x);
        isChecked[x] = true;

        // count 세기
        int count = 0;

        // queue에 담겨진게 없을 때까지
        while(!queue.isEmpty()) {
            // 현재 queue 사이즈만큼 queue에서 index를 알아내, 해당 index와 연결된 도시들을 queue에 추가
            int queueSize = queue.size();
            for(int i=0;i<queueSize;i++) {
                ArrayList<Integer> list = lists[queue.poll()];
                for(int j=0;j<list.size();j++) {
                    // 해당 index와 연결된 도시들을 queue에 추가
                    int newIndex = list.get(j);
                    if(!isChecked[newIndex]) {
                        isChecked[newIndex] = true;
                        queue.add(newIndex);
                    }
                }
            }
            // count 증가 후, 비교를 통해 원하는 이동 값과 동일해질 경우 break
            count++;
            if(count == K) {
                break;
            }
        }

        // 만약, count가 동일하고 큐가 비어있지 않으면 해당 값들 출력
        if(count == K && !queue.isEmpty()) {
            int [] outputs = new int[queue.size()];
            for(int i=0;i<outputs.length;i++) {
                outputs[i] = queue.poll();
            }

            // 정렬해서 오름차순으로 출력
            Arrays.sort(outputs);
            for(int i=0;i<outputs.length;i++) {
                bw.write(outputs[i]+1 + "\n");
            }
        }
        // 그렇지 않으면 -1 출력
        else {
            bw.write(-1 + "\n");
        }
    }
}