[백준 Gold 2] 1766 문제집 - Java

문제링크 : https://www.acmicpc.net/problem/1766

1766번: 문제집

 

접근 과정 : 

• 결국 먼저 풀어야하는 문제가 없고, 문제 번호가 작은 것부터 출력하면 된다.
• 문제는 2가지 방법으로 접근했다.

 

   1.

• 해당 문제를 기준으로, 먼저 풀어야 하는 문제와 나중에 풀어야 하는 문제를 저장하는 List 2개를 이용해서 접근
• 우선순위 큐에는 현재 풀 수 있는 문제를 집어넣어서, 문제 번호가 작은 것부터 풀었다.
• 문제를 풀 때, 해당 문제보다 나중에 풀어야 하는 문제가 있다면, 그 문제의 before List에서 해당 문제를 제거.
• 만약 beforeList의 사이즈가 0이라면 문제를 풀 수 있으므로, 우선순위 큐에 삽입했다.
• => 양방향 링크를 모두 저장해야 하고, 매 순간 삭제 연산이 들어가기때문에 리소스가 많이 필요하다.

 

   2. 

• 문제 번호와, 다음 문제를 가르키는 노드를 사용해서 접근.
• 따로 먼저 풀어야하는 문제의 개수를 저장하는 배열도 사용.
• 먼저 풀어야하는 문제가 == 0 이라면 우선순위 큐에 삽입
• 문제를 풀 때, 다음 문제들에 접근하면서 beforeCnt를 -1 수행
• 만약 beforeCnt가 0이라면 풀 수 있으므로, 우선순위 큐에 삽입
• => 확실히 다음을 가리키는 포인터? 구조다 보니 접근이 빠른것 같다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    문제집
	
    List<HashSet> bofore / afetr를 사용
*/

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

public class BOJ1766 {

    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());

        List<Set<Integer>> before = new ArrayList<>();
        List<Set<Integer>> after = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i <= N; i++) {
            before.add(new HashSet<>());
            after.add(new HashSet<>());
        }

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            before.get(b).add(a);
            after.get(a).add(b);
        }

        for (int i = 1; i <= N; i++) {
            if (before.get(i).isEmpty()) {
                pq.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {

            int question = pq.poll();

            for (int next : after.get(question)) {
                if (before.get(next).size() == 1) {
                    pq.add(next);
                }
                before.get(next).remove(question);

            }

            sb.append(question).append(" ");
        }

        System.out.println(sb.toString().trim());
    }

}

 

 

package BOJ;

/* 
    문제집
	
    Node 클래스인 Question를 생성해서 사용
*/

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

public class BOJ1766_copy {

    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());

        Question[] qArr = new Question[N + 1];
        int[] beforeCnt = new int[N + 1];

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            qArr[a] = new Question(b, qArr[a]);
            beforeCnt[b]++;
        }

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

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

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            
            int num = pq.poll();

            sb.append(num).append(" ");

            for(Question question = qArr[num]; question!=null; question = question.before){
                beforeCnt[question.num]--;
                if (beforeCnt[question.num] == 0) {
                    pq.add(question.num);
                }
            }

        }

        System.out.println(sb.toString().trim());
    }

    private static class Question {

        int num;
        Question before;

        Question(int num, Question before) {
            this.num = num;
            this.before = before;
        }
    }
}

 

P.S 

문제에 따라서, 필요에 따라서 class를 생성해서 사용하고, 트리의 개념도 좀 더 수월하게 적용할 수 있어야 하는데..