[BOJ] 1766번 문제집

개요

우선순위 큐와 위상 정렬을 이용해 풀 수 있는 문제

문제링크

코드

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Baekjoon1766 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<Integer>[] nextProblem = new ArrayList[n+1];
        for (int i = 0; i < n+1; i++) 
            nextProblem[i] = new ArrayList<>();
        int[] prevProblemCount = new int[n+1];
    
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            nextProblem[a].add(b);
            prevProblemCount[b]++;
        }

        for (int i = 1; i < n+1; i++) { 
        //이전에 풀어야 하는 문제가 없는 문제를 우선순위 큐에 삽입
            if(prevProblemCount[i] == 0) {
                pq.add(i);
            }
        }
        
        while(!pq.isEmpty()) {
            int currItem = pq.poll();
            for (int i = 0; i < nextProblem[currItem].size(); i++) {
                int nextItem = nextProblem[currItem].get(i);
                prevProblemCount[nextItem]--;
                if(prevProblemCount[nextItem] == 0)  
                    pq.add(nextItem);
            }
            bw.write(currItem+" ");
        }
        bw.newLine();
        bw.flush();
    }
}

해결 과정

처음에는 각 문제마다 먼저 풀어야 하는 문제(prevProblem[])를 저장하고 각 문제 풀고나서 쉽게 풀리는 문제(nextProblem[])를 ArrayList에 저장해 우선순위 큐에 집어넣어 하나하나 살펴보는 방식으로 구현하였다.

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    StringTokenizer st;

    st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    ArrayList<Integer>[] nextProblem = new ArrayList[n+1];
    for (int i = 0; i < n+1; i++) 
        nextProblem[i] = new ArrayList<>();
    int[] prevProblem = new int[n+1];
    boolean[] isSolved = new boolean[n+1];
    
    for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        nextProblem[a].add(b);  //a문제를 풀고나서 쉽게 풀리는 b 문제 저장
        prevProblem[b] = a; //b문제 이전에 먼저 풀면 쉽게 풀리는 문제 a 저장
    }

    for (int i = 1; i < n+1; i++) { 
    //이전에 풀어야 하는 문제가 없는 문제를 우선순위 큐에 삽입
        if(prevProblem[i] == 0) {
            pq.add(i);
            isSolved[i] = true;
        }
    }
    
    while(!pq.isEmpty()) {
        int currItem = pq.poll();
        for (int i = 0; i < nextProblem[currItem].size(); i++) {
            int nextItem = nextProblem[currItem].get(i);
            if(nextItem != 0 && !isSolved[nextItem])  {
                pq.add(nextItem);
                isSolved[nextItem] = true;
            }
        
        }
        bw.write(currItem+" ");
    }
    bw.newLine();
    bw.flush();
}

하지만 이 방법으로는 통과가 되지 않았다.

그래서 다시 생각해보니 선행해서 풀어야 하는 문제가 여러개일 경우 그 문제들을 모두 풀어야 다음 문제를 풀 수 있다는 사실을 알았다.

그래서 코드를 조금 고쳐서 prevProblem배열에 선행해서 풀어야할 문제를 적지말고 선행해서 풀어야할 문제의 갯수를 저장하고 우선순위 큐에서 문제를 빼낼 때마다 해당문제를 선행으로 가지는 문제의 prevProblem갯수를 마이너스해주는 방식으로 수정해서 통과됐다.

결과