[코테] 백준 2252번 : 줄 세우기 (java)

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

알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프

❓문제

---

🔅해석

위상정렬을 이용하여 풀이한다.

 

위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다.

 

// input
4 2
4 2
3 1

 

1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다.

 

 

2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다.

 

 

3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다.

 

 

4. Queue가 빌 때까지 반복한다.

---

⭕정답 코드

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

public class Main {

	static int N, M;
	static ArrayList<Integer>[] adjList;
	static int[] indegree;
	static Queue<Integer> que;
	static StringBuilder sb = new StringBuilder();

	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());

		adjList = new ArrayList[N];
		for (int n = 0; n < N; n++) {
			adjList[n] = new ArrayList<>();
		}

		que = new LinkedList<>();
		indegree = new int[N];

		// 1. in-degree 계산
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;

			adjList[a].add(b);
			indegree[b]++;
		}

		for (int i = 0; i < N; i++) {
			if (indegree[i] == 0) {
				que.add(i);
			}
		}

		// 2. loop
		while (!que.isEmpty()) {

			int node = que.poll();
			sb.append(node + 1).append(" ");

			for (Integer i : adjList[node]) {
				indegree[i]--;
				if (indegree[i] == 0) {
					que.offer(i);
				}
			}

		}

		System.out.println(sb.toString());
		br.close();
	}
}

 

---

❗결과