[ 백준 ] 1766 문제집

📌 Problem

1766번 문제는 1번부터 N번까지의 node 들을 번호 순서들로 탐색하지만 동시에 주어진 선후 관계 조건을 지키면서 탐색하는 문제이다. 선후 관계 조건 탐색은 위상 정렬 알고리즘(Topological Sorting) 알고리즘을 통해 해결할 수 있다. 다만, 탐색이 가능한 node 중에서 번호가 낮은 노드를 먼저 탐색하기 때문에 우선순위 큐를 추가로 사용한다.

📌 Solution

Step 1. 첫 번째 줄을 읽고 필요한 자료구조를 초기화한다.

- degrees[node]는 node를 탐색하기 위해 사전에 탐색해야 하는 node의 개수이다.

- nextNodes.get(node)는 node가 사전 탐색 대상이 되는 node의 목록이다.

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());

int[] degrees = new int[N + 1];
Map<Integer, Set<Integer>> nextNodes = IntStream.rangeClosed(1, N).boxed()
        .collect(Collectors.toMap(i -> i, i -> new HashSet<>()));

Step 2. M개의 선후관계를 읽으면서 degrees와 nextNodes의 값을 업데이트한다.

- pre와 post는 선후관계 node 값이다.

int pre, post;
while (M-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    pre = Integer.parseInt(tokenizer.nextToken());
    post = Integer.parseInt(tokenizer.nextToken());
    degrees[post]++;
    nextNodes.get(pre).add(post);
}

Step 3. PriorityQueue를 통해 사전 탐색이 완료된 node들을 탐색한다.

- readied는 사전 탐색이 완료된 (degrees 값이 0) node 들을 번호 순서대로 저장하는 우선순위 큐이다.

- readied에서 가장 작은 node를 출력하고 자신을 사전 탐색 node로 가지는 node들의 degrees를 1 감소시킨다.

- 이 때 감소된 degree가 0인 node는 우선순위 큐에 삽입한다.

Queue<Integer> readied = IntStream.rangeClosed(1, N).filter(n -> degrees[n] == 0).boxed()
        .collect(Collectors.toCollection(PriorityQueue::new));
while (!readied.isEmpty()) {
    int node = readied.poll();
    result.append(node).append(" ");
    for (int next : nextNodes.get(node)) if (--degrees[next] == 0) readied.offer(next);
}

📌 Code

void solve() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int N = Integer.parseInt(tokenizer.nextToken());
    int M = Integer.parseInt(tokenizer.nextToken());

    int[] degrees = new int[N + 1];
    Map<Integer, Set<Integer>> nextNodes = IntStream.rangeClosed(1, N).boxed()
            .collect(Collectors.toMap(i -> i, i -> new HashSet<>()));

    int pre, post;
    while (M-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        pre = Integer.parseInt(tokenizer.nextToken());
        post = Integer.parseInt(tokenizer.nextToken());
        degrees[post]++;
        nextNodes.get(pre).add(post);
    }

    Queue<Integer> readied = IntStream.rangeClosed(1, N).filter(n -> degrees[n] == 0).boxed()
            .collect(Collectors.toCollection(PriorityQueue::new));
    while (!readied.isEmpty()) {
        int node = readied.poll();
        result.append(node).append(" ");
        for (int next : nextNodes.get(node)) if (--degrees[next] == 0) readied.offer(next);
    }
}