링크

2252 줄 세우기

문제

풀이

이 문제는 대표적인 위상정렬 문제이다.
위상정렬이란 자세한건 이 블로그를 참고하자

위상정렬의 핵심은 사이클이 없어야 하며 방향이 있는 그래프이다.
이 문제처럼 순서가 있다면 위상정렬을 통해 순서를 정할 수 있다.
위상정렬은 진입차수를 카운트 배열하고 방향그래프이므로 나가는 노드들을 다 저장해야 한다.
그래서 진입차수가 0이 되면 queue에 넣어주고 queue에서 노드를 하나 빼서 그 노드에서 이동할 수 있는 노드들의 뺀다. 뺀 노드들을 진입차수 카운트를 하나씩 깎고 만약 그 노드의 진입차수가 0이 된다면 queue에 넣어주면 된다.
블로그를 통해서 따라가면서 직접 해보면 생각보다 쉽다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		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[] nodeInputCount = new int[n+1];
		
		//인접한 노드들의 배열
		List[] list = new ArrayList[n+1];
		for(int i=0;i<list.length;i++) list[i] = new ArrayList<>();
		
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
		
			list[a].add(b);
			nodeInputCount[b]++; 
		}

//		System.out.println(Arrays.toString(nodeInputCount));
//		for(int i=0;i<list.length;i++) System.out.println(list[i]);
		
		StringBuilder sb = new StringBuilder();
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1;i<nodeInputCount.length;i++) {
			if(nodeInputCount[i] == 0) {
				queue.add(i);
				sb.append(i).append(" ");
			}
		}
		
		while(!queue.isEmpty()) {
			int node = queue.poll();
			
			for(int i=0;i<list[node].size();i++) {
				int idx = (int)list[node].get(i);
				
				nodeInputCount[idx]--;
				if(nodeInputCount[idx] == 0) {
					queue.add(idx);
					sb.append(idx).append(" ");
				}
			}
			
		}
		
		System.out.println(sb.toString());
	}
}