[JAVA]백준 2252번 - 줄 세우기

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

package baekjoon;

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

public class b2252 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int indegree[] = new int[n+1];
		
		ArrayList<Integer>list[] = new ArrayList[n+1];
		for(int i = 1; i <= n ;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);
			indegree[b]++;
		}
		
		Queue<Integer> q = new LinkedList<>();
		for(int i = 1 ; i <= n ; i++) {
			if(indegree[i] == 0) {
				q.offer(i);
			}
		}
		
		while(!q.isEmpty()) {
			int tmp = q.poll();
			bw.write(tmp+" ");

			for(int i = 0 ; i < list[tmp].size(); i++) {
				int next = list[tmp].get(i);
				indegree[next]--;
				
				if(indegree[next] == 0) {
					q.offer(next);
				}
			}
		}
		bw.close();
	}
	
}

3 2
1 3
2 3

이 입력에서 1번이 3번보다 앞에 서고, 2번이 3번보다 앞에 서야하잖아요

이렇게 되면 그래프를 그릴 수 있는데

위상정렬이라고 방향성은 있는데 사이클은 없어야하는 그래프에서 할 수 있는? 정렬이 있는데 고걸 사용하면 됩니다

위상정렬 Topological Sort (Java) :: 뱀귤 블로그 (tistory.com)

이 선생님 글 보면서 공부했는데

 

자기를 가리키고 있는 선들의 수를 indegree에 저장한 상태에서

indegree가 0인 노드들을 큐에 넣고

다른 노드들의 indegree를 전부 1씩 빼주면서

또 이때 1 빼면서 0이 된 노드들 큐에 넣어주고

이거 계속 반복해주면 됩니다