1766 : 문제집

1766 : 문제집

문제를 예시로 들고 있지만, 그래프에서 정점의 순서를 정해야 하는 문제이다. 문제에 나온 조건마다 필요한 자료구조, 알고리즘은 다음과 같다.

1. N개의 문제는 모두 풀어야 한다. : 완전 탐색
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. : 우선순위 큐
3. 가능하면 쉬운 문제부터 풀어야 한다. : 위상 정렬

입력

문제를 입력 받을 때 다음과 같이 데이터를 저장한다. (4, 2) (4, 3)가 입력으로 들어오면 problem[4]는 {2, 3}이고, 2와 3은 4를 먼저 풀어야 하므로 needed가 1이다.

static List<Integer>[] problems; // 문제를 풀고 나서 풀 수 있는 문제들의 목록
static int[] needed; // 문제를 풀기 위해 먼저 풀어야 하는 문제의 수

// input problems
for(int i = 0; i < N; i++) problems[i + 1] = new ArrayList<>();
for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int fp = Integer.parseInt(st.nextToken());
    int sp = Integer.parseInt(st.nextToken());

    problems[fp].add(sp); needed[sp]++;
}

BFS

우선순위 큐를 이용해서 모든 정점들을 탐색한다. 먼저 풀어야 할 문제가 없는, 위상 정렬 차수가 0인 문제를 먼저 넣어야 한다. 이때 우선순위 큐를 이용하기 때문에 숫자가 작은 것을 먼저 처리한다. 자연스럽게 조건 3번의 가능하면 쉬운 문제부터 풀어야 한다를 만족한다.

우선순위 큐를 탐색하면서 해당 문제를 선행 문제로 가지고 있는 문제들의 차수를 줄인다. 앞선 예시를 기준으로 설명하면, 문제 4를 풀고 나면 problems[4]를 순회하면서 문제 2, 3의 차수를 줄이는 것이다.

(4, 2) (4, 3)가 입력으로 들어오면 problem[4]는 {2, 3}이고, 2와 3은 4를 먼저 풀어야 하므로 needed가 1이다.

problem를 순회하며 needed가 0인 다음 문제들을 우선순위 큐에 추가한다. 이 작업을 반복하여 조건 1번의 문제를 모두 풀어야 한다는 조건을 만족한다.

static void BFS() {
    // needed less, priority high
    Queue<Integer> pq = new PriorityQueue<>();
    for(int i = 1; i <= N; i++) { if(needed[i] == 0) pq.add(i); }

    // BFS
    while(!pq.isEmpty()) {
        int curr = pq.poll();
        un_needed(curr);
        answer.append(curr + " ");

        for(int pb : problems[curr]) {
            if(needed[pb] == 0) pq.add(pb);
        }
    }
}

static void un_needed(int curr) {
    for(int pb : problems[curr]) { needed[pb]--;}
}

cpp 풀이 java 풀이 python 풀이

시간 복잡도

BFS 부분이 시간 복잡도에서 가장 큰 비중을 차지한다. 위상 정렬을 위해서 모든 문제들을 확인하면서 각 문제에서 다음 문제들을 제거하므로, 위상 정렬만 생각했을 때 시간 복잡도는 O(N + M)이다.

이 문제에서는 가능하면 쉬운 문제부터 풀어야 하는 조건에 의해 큐가 아니라 우선순위 큐를 사용하므로, 노드를 넣고 빼는 데에 log N의 시간이 소요된다. 따라서 최종적인 시간 복잡도는 O((N+M)logN)이다.