[백준] 줄세우기 2252 - java

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

2252번: 줄 세우기

public class 줄세우기 {
	static int N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int inDegree[] = new int[N+1];
		Queue<Integer> q = new LinkedList<Integer>();
		ArrayList<Integer> adj[] = new ArrayList[N+1];
		
		for(int i=1; i<=N; i++) {
			adj[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj[a].add(b);
		}
		
		for(int i=1; i<=N; i++) {
			for(int v : adj[i]) {
				inDegree[v]++;
			}
		}
		
		for(int i=1; i<=N; i++) {
			if(inDegree[i] == 0) {
				q.offer(i);
			}
		}
		
		StringBuilder result = new StringBuilder();
		for(int i=1; i<=N; i++) {
			if(q.isEmpty()) {
				return;
			}
			int cur = q.poll();
			result.append(cur).append(" ");
			
			for(int v : adj[cur]) {
				inDegree[v]--;
				if(inDegree[v] == 0) q.offer(v);
			}
		}
		System.out.println(result.toString());
	}
}

위상정렬 문제입니다.

3만2천개의 정점, 10만개의 간선이어 인접리스트로 선언했습니다.

1. 인접리스트에 입력을 받고 진입차수가 0인 정점들을 q에 넣습니다.

2. q에서 값을 하나 빼고, 그 값과 연결된 정점들의 진입차수를 하나씩 감소시킵니다.

3. 감소된 값이 0이면 q에 넣습니다.

2~3을 반복하여 결괏값을 구합니다.