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

문제

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

풀이

• N명의 학생들을 키 순서대로 줄을 세우려고 한다.
• 두 학생의 키를 비교하는 방법을 사용하여 키를 세울 것이다.
• 일부 학생들의 키만을 비교하여 줄을 세운다.
• 두 학생의 번호 A, B가 주어지면, 이는 학생 A가 B의 앞에 서야 한다는 의미이다.

전형적인 위상 정렬 문제입니다.

인접리스트를 사용하여 a, b가 주어지면 a인덱스에 b를 추가하고 b 앞에 한 사람이 추가됨을 나타내면 쉽게 풀 수 있는 알고리즘입니다.

	private static void init() {
		ind = new int[n+1];
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
	}

• ind: 본인 앞에 몇 명이 존재하는지 알 수 있는 배열
• graph: 본인 뒤에 존재하는 사람들의 목록을 저장할 배열

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			++ind[b];
		}

• 입력 받을 때 이런 식으로 값을 저장해 주면 됩니다.

	private static void topology() {
		res = new ArrayList<>(); // 학생들의 키 순서를 나타낼 배열
		Queue<Integer> queue = new ArrayDeque<>();
		
        // 이미 앞에 아무도 없는 사람들이면 queue에 추가
		for (int i = 1; i <= n; i++) {
			if (ind[i] == 0) {
				queue.add(i);
			}
		}
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			res.add(cur); // 이미 앞에 아무도 없으므로 정답 배열에 추가
			
            // 본인보다 작은 사람들 탐색
			for (int v : graph.get(cur)) {
				--ind[v];
				if (ind[v] == 0) {
					queue.add(v);
				}
			}
		}
		
	}

• 본인보다 뒤에 있는 사람들을 탐색할 때, ind[v]를 감소시키는 이유는 이미 본인보다 앞에 있는 사람이 정답 배열에 추가가됨으로써, 이 사람을 고려할 필요가 없어졌기 때문입니다.
• ind는 나보다 앞에 있는 사람이 몇 명인가?를 나타내는 배열입니다.
• 첫 번째 코멘트가 이해가 되지 않으신 분들은 이를 고려해서 코드를 다시 보시면 이해가 가실 겁니다.

코드

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

public class Main_2252 {
	static int n, m;
	static int[] ind;
	static List<Integer> res;
	static List<ArrayList<Integer>> graph;
	
	private static void init() {
		ind = new int[n+1];
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
	}
	
	private static void topology() {
		res = new ArrayList<>();
		Queue<Integer> queue = new ArrayDeque<>();
		
		for (int i = 1; i <= n; i++) {
			if (ind[i] == 0) {
				queue.add(i);
			}
		}
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			res.add(cur);
			
			for (int v : graph.get(cur)) {
				--ind[v];
				if (ind[v] == 0) {
					queue.add(v);
				}
			}
		}
		
	}
	
	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());
		
		init();
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			++ind[b];
		}
		
		topology();
		
		for (int v : res) System.out.print(v + " ");
	}

}