[백준/Java] 2252 줄 세우기

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

문제 요약

두 학생의 키를 비교한 결과가 M개 주어진다.
A B 형태로 주어지면 A가 B 앞에 서야 한다는 뜻이다.
앞선 정보를 활용해 N명의 학생을 키 순서대로 줄을 세운다.
이때 답이 여러 가지인 경우에는 아무거나 출력한다.

학생의 수 N은 최대 3만 2천이다.
키를 비교한 횟수 M은 최대 10만이다.

---

문제 접근

이 문제는 처음에 딱 봤을 때 어떻게 풀어야할 지 고민이 되는 문제이다.
놀랍게도 이 문제도 위상 정렬을 이용해 해결할 수 있다.

M번의 키 비교를 입력받으면서 A(앞에 서는 학생)가 B(뒤에 서는 학생)를 가리키는 방향으로 설정한다.
이후 나를 가리키는 것이 없는, 즉 나보다 키가 작은 경우가 없는 학생부터 순서대로 줄을 세우면 된다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	static int N, M;
	static int[] numTargeted;
	static ArrayList<Integer>[] target;
	
	static StringBuilder answer = new StringBuilder();
	
	// 입력 받기
	public static void getInput() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());
		
		// 나를 가리키는 수를 나타내는 배열(numTargeted) 초기화
		numTargeted = new int[N+1];
		for (int i = 0; i < N+1; i++) {
			numTargeted[i] = 0;
		}
		
		// 내가 가리키는 것을 나타내는 리스트(target) 초기화
		target = new ArrayList[N+1];
		for (int i = 0; i < N+1; i++) {
			target[i] = new ArrayList<>();
		}
		
		// 나를 가리키는 수를 더해주고, 내가 가리키는 것 또한 추가해줌
		for (int i = 0; i < M; i++) {
			StringTokenizer stm = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(stm.nextToken());
			int B = Integer.parseInt(stm.nextToken());
			
			numTargeted[B]++;
			
			target[A].add(B);
		}
	}
	
	// 위상정렬을 통해 문제를 해결하기
	public static void topolSort() {
		
		ArrayDeque<Integer> que = new ArrayDeque<>();
		
		// 나를 가리키는 것이 0이면 큐에 넣음
		for (int i = 1; i < N+1; i++) {
			if (numTargeted[i] == 0) {
				que.add(i);
			}
		}
		
		while (que.size() > 0) {
			// 큐에서 값을 하나 꺼냄
			int now = que.poll();
			
			// 그 값을 정답에 넣음
			answer.append(now+" ");
			
			// 내가 가리키는 것들의 값을 1씩 빼줌
			// 만약 1을 빼서 그 값이 0이 되었다면 큐에 넣음
			while (target[now].size() > 0) {
				int tg = target[now].remove(0);
				numTargeted[tg]--;
				
				if (numTargeted[tg] == 0) {
					que.add(tg);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		// 입력 받기
		getInput();
		
		// 위상정렬을 통해 문제를 해결하기
		topolSort();
		
		// 정답 출력
		System.out.println(answer);
	}
 }

---

회고

(추가 예정)