[BOJ-1766][위상정렬] 문제집 -Java

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

1766번: 문제집

package BOJ_위상정렬;

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class boj_1766_문제집 {
	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 []weight=new int[N+1];
		boolean[] visited = new boolean[N+1];
		List<Integer> list[]=new List[N+1];
		List<Integer> result=new ArrayList<>();
		PriorityQueue<Integer> node = new PriorityQueue<>();
		
		for(int i=0; i<=N; i++) {
			list[i]=new ArrayList<>();
		}
		
		for(int i=0; i<M; i++) {
			st= new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			list[start].add(end);
			weight[end]++;
		}
		
		
		
		for(int i=1; i<=N; i++) { //진입이 0인 숫자 찾기
			if(weight[i]==0) {
				node.add(i);
			}
		}
		
		while(!node.isEmpty()) {
			int size=node.size();
			
			for(int i=0; i<size; i++) {
				int cur=node.poll();
				result.add(cur); //순서
				
				//n과 연결된 간선 모두 끊어주고
				for(int j=0; j<list[cur].size(); j++) {
					int next=list[cur].get(j);
					if(--weight[next]==0) node.add(next);
				}
			}
		}
		
		for(int num:result) {
			System.out.print(num+" ");
		}
		
	}

}

소요시간 : 30분

 

위상 정렬을 이용해 풀 수 있다!

 

주의할 점은 그냥 큐를 쓰면 안 되고 우선순위 큐를 써야 한다는 점이다!

 

둘 다 풀 수있는 문제라면 순서가 더 빠른 문제를 풀어야 하기 때문이다!

 

만약 위상정렬을 잘 모른다면 이곳에서 공부할 수 있다ㅎ

dkwjdi.tistory.com/146

위상정렬

 

 

끝~