백준_문제집_1766

문제 링크

조건

•  N  : 문제 개수, 1~32,000개
•  M  : 선행 관계 조건 수, 1~100,000개

 

접근 방법

• count 배열에 문제마다 선행해서 풀어야 할 문제 수 저장
• info 리스트에 문제마다 선행해서 풀어야 할 문제 번호 리스트 저장

 

솔루션

public class Main {

	//Gold2
	static int N,M;
	static int[] count;//선행되어야 할 문제 카운트
	static List[] info;//선행되어야 할 문제 정보
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		N = Integer.parseInt(st.nextToken());//문제 개수
		M = Integer.parseInt(st.nextToken());//info 개수
		
		info = new ArrayList[N+1];
		count = new int[N+1];
		for(int i = 1; i < N+1; i++) {
			info[i] = new ArrayList<Integer>();
		}
		
		
		int f,l;
		while(M-- > 0) {//선행정보 저장
			st = new StringTokenizer(br.readLine().trim(), " ");
			f = Integer.parseInt(st.nextToken());//선행
			l = Integer.parseInt(st.nextToken());//후행
			count[l]++;
			info[f].add(l);//f 풀면 l 쉽게 풀림
		}

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for(int i = 1; i < N+1; i++) {
			if(count[i] == 0) {
				queue.offer(i);
			}
		}
		
		//priorityQueue 사용 => O(NlogN)..?? : 500ms
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			sb.append(cur).append(" ");
			count[cur] = -1;//푼 문제 체크
			for(int j = 0, size = info[cur].size(); j < size; j++) {
				int next = (int)info[cur].get(j);
				if(--count[next] == 0) queue.offer(next);
			}
			
		}
		
		//중첩for문 => O(N2) : 700ms
//		int cnt = 0;
//		while(cnt < N) {
//			for(int i = 1; i < N+1; i++) {
//				if(count[i] == 0) {
//					sb.append(i).append(" ");
//					count[i] = -1;//푼 문제 체크
//					for(int j = 0, size = info[i].size(); j < size; j++) {
//						count[(int)info[i].get(j)]--;
//					}
//					break;
//				}
//			}
//			cnt++;
//		}
		
		System.out.println(sb.toString());
	}

}

 

리뷰

• 처음에 priorityQueue를 사용 안하고 중첩 for문 돌림 => pq를 썼을때보다 200ms정도 차이남!