백준 - 문제집(1766)

오늘 풀어본 문제는 문제집이다.

호가롭게 도전했지만 실패한 문제이다...

1. 문제요약

• 문제집을 푸는 순서를 정하는 문제이다.
• 입력은 풀어야 할 문제의 수(N) 선행해서 풀어야 할 문제 케이스의 수 (M)이 주어진다.
• 일반적으로 문제는 오름차순 형태로 풀어야 한다.
• 입력에서 특별히 내림차순 형태의 선행해야 할 문제 케이스를 준다.
  ex) 4 2 : 2번 문제보다 4번 문제를 선행해서 풀어야 함.
  

2. 나의 풀이

나는 dp 방식으로 풀어보려 했다.

1. 각 문제마다 선행되어야 하는 인접 리스트를 생성한다.
2. for문으로 1부터 N까지 돌며 findValue 함수를 호출한다. (인자 = i)
   2-1. 2번에서 호출한 i로 findAlone 함수를 호출한다.
   2-2. 인접리스트.get(i)에 해당하는 원소들을 다시 findAlone 함수로 호출한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static Set <Integer> answer;
    static boolean visited [];
    static List<PriorityQueue<Integer>> pqList;
    static int max=1;
    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());

        answer = new LinkedHashSet<>();
        visited = new boolean[N+1];
        pqList = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            pqList.add(new PriorityQueue<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int pre = Integer.parseInt(st.nextToken());
            int post = Integer.parseInt(st.nextToken());
            pqList.get(post).add(pre);
        }

        for(int i=1; i<=N; i++) {
            findValue(i);
        }
        // Set 요소 출력
        for (int value : answer) {
            System.out.print(value+" ");
        }

    }

    static void findValue(int index) {
        if(visited[index]) return;
        visited[index] = true;
        int size = pqList.get(index).size();

        for(int i=1; i<=size; i++) {
            int value = pqList.get(index).poll();
            findAlone(value);
            findValue(value);
            answer.add(value);
        }
        answer.add(index);
    }

    static void findAlone(int index) {
        for(int i=max; i<index; i++){
            if ((pqList.get(i).size() == 0) && !visited[i]) {
                max = i;
                answer.add(i);
                visited[i] = true;
            }
        }
    }
}

3. 정답풀이

위상정렬을 이용하는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 [] indegree = new int[N+1];
        List<Integer> [] quizZip = new List[N+1];

        for (int i = 0; i <= N; i++) {
            quizZip[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int pre = Integer.parseInt(st.nextToken());
            int post = Integer.parseInt(st.nextToken());
            quizZip[pre].add(post);
            indegree[post]++;
        }

        StringBuilder sb = new StringBuilder();
        PriorityQueue <Integer> pq = new PriorityQueue<>();

        for(int i=1; i<=N; i++){
            if(indegree[i]==0){
                pq.add(i);
            }
        }

        while (!pq.isEmpty()){
            int now = pq.poll();
            sb.append(now+" ");

            for(int i=0; i<quizZip[now].size(); i++){
                int next = quizZip[now].get(i);
                indegree[next]--;
            }

        }

        System.out.println(sb);
    }

}

위상정렬 개념 정리 : https://bcp0109.tistory.com/21