[PS] 백준 1766 문제집 java 풀이

1766번: 문제집 (acmicpc.net)

처음 틀린 풀이와 코드

1. 배열을 만들어서 각 인덱스에 먼저 풀어야되는 문제 값을 넣고
2. 그 배열을 순회하면서 먼저 풀어야하는 문제가 있으면 먼저 출력,
3. 나중에 먼저 풀었던 문제는 순회에서 넘어감

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N + 1];
		int numOfGood = Integer.parseInt(st.nextToken());

		//  먼저풀어야함 나중에 풀어야함
		for (int i = 0; i < numOfGood; i++) {
			st = new StringTokenizer(br.readLine());
			int first = Integer.parseInt(st.nextToken());
			int after = Integer.parseInt(st.nextToken());
			arr[after] = first;
			arr[first] = -1; // 스킵하도록 마킹
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < N + 1; i++) {
			if (arr[i] != 0 && arr[i] != -1) sb.append(arr[i]).append(" ");
			else if (arr[i] == -1) continue;
			sb.append(i).append(" ");
		}

		System.out.println(sb);

문제점 분석

1. 의존성 관리 부족: arr 배열로 의존 관계를 관리하는 방식은 문제 간의 의존성(선행 조건)을 정확히 반영하지 못합니다. 각 문제 간에 여러 개의 의존 관계가 있을 수 있는데, 단일 배열로 이를 관리하는 것은 어려움이 있습니다.
2. 위상 정렬 미사용: 현재 코드는 순서를 위상 정렬로 처리하지 않고, 단순히 배열을 순차적으로 검사하여 출력하는 방식입니다. 이는 의존 관계가 복잡할 경우, 올바른 순서를 보장하지 못합니다. 문제에서 요구하는 의존 관계를 기반으로 문제를 풀 순서를 결정해야 하므로, 위상 정렬 알고리즘을 사용하는 것이 적합합니다.
3. 우선 순위 미반영: 문제에서는 가능한 한 쉬운 문제(번호가 작은 문제)를 먼저 풀어야 한다고 명시되어 있습니다. 이를 반영하려면 우선순위 큐(Priority Queue)를 사용하여 처리하는 것이 적합합니다.

위상 정렬

위상 정렬(Topological Sort)이란 사이클이 없는 방향 그래프(Directed Acyclic Graph, DAG)에서 노드들 간의 선후 관계를 유지하면서 모든 노드를 정렬하는 알고리즘입니다.

위상 정렬의 대표적인 알고리즘은 다음과 같습니다.

• 진입 차수(Indegree) 기반 알고리즘: 각 노드의 진입 차수를 계산하고, 진입 차수가 0인 노드부터 차례대로 처리합니다. 노드를 처리할 때 그 노드와 연결된 다른 노드들의 진입 차수를 감소시키며, 다시 진입 차수가 0이 된 노드를 처리하는 방식입니다. 이 과정은 BFS(너비 우선 탐색) 방식으로 구현됩니다.
• DFS(깊이 우선 탐색) 기반 알고리즘: 각 노드를 방문하면서 후손 노드를 먼저 처리한 후 현재 노드를 처리하는 방식으로, 후위 순회를 사용하여 정렬할 수 있습니다.

다시 문제 풀이

1. 위상 정렬을 하기 위해 int[] indegree와, 인접 리스트를 만들기 위한 ArrayList<Integer>[] 를 만든다.
2. 인접 리스트에서 먼저 풀어야할 문제의 번호에 해당하는 인덱스에, 나중에 풀어야하는 문제 수를 삽입한다.
3. 그리고 나중에 풀어야하는 문제 번호에 해당하는 인덱스에 indegree를 + 1한다. 
4. 우선순위 큐를 만들어서, indegree가 0인 문제 번호들을 삽입한다. 즉, 가장 먼저 풀어야하는 문제들중에서 작은 수(쉬운 문제를)로 정렬되게 된다.
5. 우선순위 큐가 빌때까지 하나씩 꺼내서 꺼낸 문제 번호의 인접 리스트에 degree를 -1씩 감소시킨다. 이 행위는 앞에 있는 작업(문제)를 끝냈다는 것 이다.
6. indegree가 0 이 되면 이 문제를 풀 차례가 되었다는 것을 의미한다. 따라서 우선순위 큐에 넣어준다.
7. while 문이 종료되면 모든 문제를 푼 것이다.

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[] indegree = new int[N + 1];
		int numOfGood = Integer.parseInt(st.nextToken());

		//  먼저풀어야함 나중에 풀어야함
		List<Integer>[] arr = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
			arr[i] = new ArrayList<>();
		}

		for (int i = 0; i < numOfGood; i++) {
			st = new StringTokenizer(br.readLine());
			int first = Integer.parseInt(st.nextToken());
			int after = Integer.parseInt(st.nextToken());
			arr[first].add(after);
			indegree[after] += 1;
		}

		//  진입 차수 (indegree) == 0인 애들 부터 삽입
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                pq.offer(i);
            }
        }

		StringBuilder sb = new StringBuilder();
		while(!pq.isEmpty()) {
			int current = pq.poll();
			sb.append(current).append(" ");
			for (int after : arr[current]) {
				indegree[after] -= 1;
				if (indegree[after] == 0) {
					pq.offer(after);
				}
			}
		}
		System.out.println(sb);

	}

}