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

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

2252번: 줄 세우기

 

---

■ 문제

---

■ 문제 이해

문제 자체는 이해하기 어렵지 않다.

첫째 줄에 학생의 수와 키를 비교한 조건의 수가 주어진다.

키를 비교할 때 학생의 번호 A B가 주어지면 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

1 3
2 3
의 정답은
[1 2 3] 또는 [2 1 3]이 될 수 있다. (1과 2의 비교 조건이 따로 없기 때문이다.)

---

■ 풀이

예제 입력 2의 상황을 그림으로 나타내면 다음과 같다.

2번 학생은 선행 작업인 4가 앞에 있어야 설 수 있고, 1번 학생도 선행 작업인 3이 앞에 있어야 설 수 있다

 

줄을 세우기 위해선 4 -> 2, 2 -> 4처럼 방향 그래프가 순환이 될 수 없으므로 예제로 주어지는 입력은 순환하지 않는 방향 그래프(DAG)가 보장된다.

 

이때, "순서가 정해져있는 작업"을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 위상 정렬 알고리즘을 통해 문제를 해결할 수 있으며 위상 정렬 알고리즘은 DAG 상황일 때만 적용이 가능하다.

 

큐(Queue)를 이용하여 위상 정렬 알고리즘을 구현해 보자.

1. 진입 차수가 0인 학생을 큐에 삽입한다.
2. 큐에서 학생을 꺼낸 후 학생과 연결된 간선을 제거한다.
3. 간선을 제거하고 제거된 학생의 진입 차수를 감소시킨 후 진입 차수가 0이 됐을 시 큐에 삽입한다.
4. 큐가 빌 때까지 2 ~ 3 과정을 반복한다.

학생마다 자기 앞에 서야 하는(선행 작업) 학생을 진입 차수로 표현한 표는 다음과 같다.

학생	1	2	3	4
진입 차수	1	1	0	0

.

아래 코드에서 1 ~ 3번에 해당하는 줄에 주석을 달아놓았다.

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

public class Main3 {
	static List<List<Integer>> nodes;
	static int[] entryCount;

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

		nodes = new ArrayList<>();
		entryCount = new int[n + 1];

		for (int i = 0; i < n + 1; i++) {
			nodes.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int front = Integer.parseInt(st.nextToken());
			int back = Integer.parseInt(st.nextToken());

			nodes.get(front).add(back);

			entryCount[back]++;
		}

		System.out.println(topologySort());
	}

	private static String topologySort() {
		StringBuilder sb = new StringBuilder();
		Queue<Integer> queue = new LinkedList<>();

		// 1번
		for (int i = 1; i < entryCount.length; i++) {
			if (entryCount[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
        	// 2번
			int current = queue.poll();
			sb.append(current).append(" ");

			for (Integer i : nodes.get(current)) {
            	// 3번
				entryCount[i]--;
				if (entryCount[i] == 0) {
					queue.add(i);
				}
			}
		}

		return sb.toString();
	}
}