백준 1766, 문제집(java)

문제 설명

민오는 1번부터 N번까지 문제를 푼다고 한다. 이때 난이도는 1번부터 N번까지 점차 올라간다. 민오가 문제를 풀 때는 몇 가지 조건이 있다.

 

1. N개의 문제는 모두 풀어야 한다.

2. 어느 한 문제에 먼저 풀어야 좋은 문제가 존재한다면 먼저 풀어야하는 문제들을 모두 풀어야 현재 문제를 풀 수 있다.

3. 문제들은 난이도가 쉬운 순으로 풀어야 한다.

 

이때 위의 조건들을 지키면서 민오가 문제를 푸는 순서를 구하라.

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

1766번: 문제집

문제 풀이

해당 문제는 위상 정렬로 푸는 문제이다.

 

위상 정렬이란 간단하게 말해서 어느 한 노드를 방문하기 전에 그 노드의 선행 노드를 모두 방문해야 한다는 조건이 걸린 문제를 푸는 알고리즘이다. 이번 문제의 2번 조건과 동일하지 않는가?

 

위상 정렬이라고 해서 이름이 어려워보이지만, 그 원리만 파악하면 간단하게 문제를 풀 수 있다.

 

본격적인 알고르짐에 들어가기 앞서 나는 arr에 해당 노드의 선행 노드의 수를 저장해줬다. 그리고 list에다가는 현재 노드를 선행 노드로 삼는 노드들(현재 노드를 방문하고 나면 방문할 가능성이 있는 노드)을 넣어줬다.

        int[] arr = new int[n];
        List<List<Integer>> list = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i=0; i<n; i++) {
            list.add(new ArrayList<>());
        }


        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[b] += 1;
            list.get(a).add(b);
        }

 

문제에서는 4와 2가 나란히 주어지면 4를 방문하면 2도 방문할 수 있다고 했다. 그렇다면 노드 2의 선행 노드는 4이니 arr[2]에 1을 더해주고 노드 4를 방문하면 노드 2를 방문할 수 있는 가능성이 생기니 list.get(4)에다가 2를 넣어줬다.

 

이제 본격적인 위상 정렬 알고리즘으로 들어가보자.

 

사실, 원리 자체는 간단한데 선행 노드의 수가 없는 노드들을 먼저 방문한다. 이때, 현재 노드와 연결된 노드들 즉, 현재 노드를 선행 노드로 가지고 있는 노드들을 하나씩 확인한다. 현재 노드를 방문했다는 의미는 선행 노드가 하나 줄어들었다는 뜻이니 연결된 노드의 선행 노드 수를 하나 줄여준다. 그리고 이때 선행 노드의 수가 0이 되서 더이상 방문해야 하는 선행 노드가 없다면 큐에 넣어준다.

 

1 -> 2

3 -> 4

3 -> 5

 

위의 예시를 들어보자면, 일단 노드 1과 3,선행 노드가 없으므로 큐에 넣어준다.

큐 : 1, 3

큐에서 노드 1을 빼온다.

큐 : 3

노드 1을 선행 노드로 삼는 노드들은 2이다. 이때 노드 1은 방문했으므로 노드 2의 선행 노드 수는 하나 줄어 0개가 된다. 그렇다면 노드 2는 더이상 선행 노드가 존재하지 않으므로(유일한 선행 노드 1을 아까 방문해줬다) 큐에 넣어준다.

큐 : 3, 2

큐에서 노드 3을 빼온다.

큐 : 2

노드 3을 선행 노드로 삼는 노드는 4와 5이다. 이때도 노드 2를 방문했으므로 4와 5의 선행 노드 수를 각각 한 개씩 줄여준다. 그렇게 되면 노드 4와 노드 5의 선행 노드는 0이 된다. 그러므로 노드 4와 노드 5 모두 선행 노드를 모두 방문해 이제 방문 가능한 노드가 되었으므로 큐에 넣어준다.

큐 : 2, 4, 5

2, 4, 5의 경우 이들을 선행 노드 삼는 노드가 없으므로 계속 poll 되다가 반복문이 끝나게 된다.

 

즉, 큐에는 오로지 모든 선행 노드를 방문하여 이제는 방문 가능한 노드들을 넣어두고 큐에서 노드를 하나 꺼낼 때마다 해당 노드를 거쳐서 가야 하는 노드들을 확인해주는 방식이다.

 

좋아, 이렇게 위상 정렬을 이용해 조건 2를 만족해줬다. 그렇다면 이제 끝난걸까? 아니, 우리에게는 조건 3이 하나 더 남았다. 바로 난이도가 작은 문제를 먼저 풀어주는 것.

 

이 부분을 해결하기 위해서는 풀 수 있는 문제들 중 가장 쉬운 문제를 먼저 꺼내줘야 한다. 즉, 큐에서 제일 작은 수를 먼저 꺼내야 한다는 것이다. 이걸 해결하기 위해서는 어떻게 해야 할까?

 

생각해보자... 무슨 자료 구조가 하나 떠오르지 않는가? 예를 들면 우선 순위... 큐... 라던가...

 

그렇다. 우선 순위 큐를 오름차순을 기준으로 사용하면 난이도가 제일 작은 문제를 먼저 나오게 해준다. 그러므로 이 문제에서는 단순한 큐가 아닌 우선 순위 큐를 이용해야 한다.

코드

java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        List<List<Integer>> list = new ArrayList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i=0; i<n; i++) {
            list.add(new ArrayList<>());
        }


        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            arr[b] += 1;
            list.get(a).add(b);
        }

        for (int i=0; i<n; i++) {
            Collections.sort(list.get(i));
        }

        for (int i=0; i<n; i++) {
            if (arr[i] == 0) {
                queue.add(i);
            }
        }

        while(!queue.isEmpty()) {
            int currentNode = queue.poll();
            List<Integer> current = list.get(currentNode);
            System.out.print((currentNode+1) + " ");

            for (int next : current) {
                arr[next] -= 1;
                if (arr[next] == 0) {
                    queue.add(next);
                }
            }

        }


    }

}