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

문제

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

---

풀이(18분)

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

public class Main {
    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()); // 도시의 개수
        int m = Integer.parseInt(st.nextToken()); // 도로의 개수
        int k = Integer.parseInt(st.nextToken()); // 거리 정보
        int x = Integer.parseInt(st.nextToken()); // 출발 도시 번호

        // 인접 리스트 초기화
        List<List<Integer>> roads = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            roads.add(new ArrayList<>());
        }

        // 도로 정보 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1; // 인덱스를 위한 -1
            int end = Integer.parseInt(st.nextToken()) - 1; // 인덱스를 위한 -1
            roads.get(start).add(end);
        }

        boolean[] visited = new boolean[n];
        Queue<Point> q = new LinkedList<>();
        List<Integer> answer = new ArrayList<>();

        q.add(new Point(x - 1, 0)); // 시작 도시
        visited[x - 1] = true;

        while (!q.isEmpty()) {
            Point point = q.poll();
            if (point.depth == k) {
                answer.add(point.start + 1); // 도시 번호 출력용 +1
                continue;
            }
            for (int next : roads.get(point.start)) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(new Point(next, point.depth + 1));
                }
            }
        }

        if (answer.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(answer);
            for (int z : answer) {
                System.out.println(z);
            }
        }
    }

    // BFS 탐색용 Point 클래스
    public static class Point {
        int start;
        int depth;

        public Point(int start, int depth) {
            this.start = start;
            this.depth = depth;
        }
    }
}

 

문제 풀이 초기 연결된 도로를 booelan[][]으로 체크했다. 하지만 이 경우 n*n에 대한 검사를 모두 진행하기 때문에 메모리 초과가 발생했다. 그렇기에 List<List<Integer>> roads = new ArrayList<>(); 를 도입하여 문제를 해결했다.