백준 1766 문제집

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다. (1이 가장 쉽고 N이 가장 어렵다)

 

내가 어떤 한 문제를 풀기 위해서는 그 문제로 들어오는 노드들 또한 풀어야만 가능하다. 즉 부모노드가 0개여야 가능하다는 뜻이다. 

부모노드가 0개인 노드들을 배열에 넣고 그중에 가장 낮은 수를 선형으로 찾으면 풀수 있을까?

N<=32000 이므로 선형 탐색을 해서는 O(N^2) 시간복잡이므로 10억이 훌쩍넘으으므로 이 방법으론 풀 수 없다.

 

배열에서 가장 빨리 최소수, 최대수를 구할수 있는것은 우선순위큐(힙)이다. (O(logN)시간에 최소 수 탐색가능)

우선순위큐를 이용하여 최소수를 구할 경우 O(N^2) 복잡도가 O(NlogN)복잡도로 줄어들게된다.

 

그러므로 다음과 같이 풀면된다. 

 

1. 부모가 0인 노드들을 우선순위큐 모두 넣어준다.

2. 우선순위큐에서 원소를 pop한다(최소수가 나오게 됨)

3-1 . 그 원소와 연결된 노드들의 부모수를 하나씩 줄인다.

3-2. 그 노드의 부모수가 0이면 풀수 있는 상태이므로 우선순위큐에 넣어준다. (2번으로 반복)

 

단, 한번 푼 문제는 또 풀면 안되므로 방문체크 배열을 하나 둬서 3-2에서 재방문 할일이 없도록 하자.

 

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

public class 문제집 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<Integer> arr[] = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		int head[] = new int[N + 1];
		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			arr[x].add(y);
			head[y]++;
		}
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for (int i = 1; i <= N; i++) {
			if (head[i] == 0)
				pq.add(i);
		}
		int ans[] = new int[N];
		int p = 0;
		boolean visited[] = new boolean[N + 1];
		while (!pq.isEmpty()) {
			int now = pq.poll();
			visited[now] = true;
			ans[p] = now;
			for (int i = 0; i < arr[now].size(); i++) {
				head[arr[now].get(i)]--;
				if (head[arr[now].get(i)] == 0 && !visited[arr[now].get(i)]) {
					pq.add(arr[now].get(i));
				}
			}

			p++;
		}
		for (int i = 0; i < N; i++) {
			System.out.print(ans[i] + " ");
		}
	}

}