[백준] 2252번 줄 세우기

JEEWOO SUL·2021년 8월 18일

💻 알고리즘

목록 보기

14/36

🔔 문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력
첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다

🎯 풀이방법

위상정렬 알고리즘을 완벽히 이해하고 있다면 쉽게 풀 수 있는 문제로 아래의 블로그를 참조하길 바란다.

velog link : 위상 정렬

⏱ 시간복잡도

O(N) = N^2

💡 이 문제를 통해 얻어갈 것

위상 정렬 알고리즘 문제

💻 Python 코드

# 백준 2252번 줄 세우기
# 위상 정렬
from collections import deque

N, M = map(int, input().split())

# 그래프 초기화
edge = [[] for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())

    # a < b
    edge[a].append(b)
    indegree[b] += 1

# 진입 차수 0인 얘들 큐에 넣기
queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append(i)

# 큐에서 1개씩 뽑으면서 연결된 간선 끊기
while len(queue)>0:
    now = queue.popleft()
    print(now, end=' ')

    # 연결된 간선 끊기
    for t in edge[now]:
        indegree[t] -= 1
        if indegree[t] == 0:
            queue.append(t)

💻 Java 코드

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 int A,B;
	
	static int[] indegree;
	static ArrayList[] edge;
	static Queue<Integer> queue;
	
	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());
		
		// ArrayList 초기화
		edge = new ArrayList[N+1];
		for(int i=1; i<=N ; i++) {
			edge[i] = new ArrayList<Integer>();
		}
		
		// 초기화
		indegree = new int[N+1];
		
		M = Integer.parseInt(st.nextToken());
		for(int m=0; m<M; m++) {
			st = new StringTokenizer(br.readLine());
			
			A = Integer.parseInt(st.nextToken());
			B = Integer.parseInt(st.nextToken());
			
			// a < b
			edge[A].add(B);
			indegree[B] += 1;
		}
		
		// 진입차수 0인 얘들 Queue에 넣기
		queue = new LinkedList<Integer>();
		for(int i=1; i<=N; i++) {
			if(indegree[i] == 0)
				queue.add(i);
		}
		
		// Queue에서 1개씩 뽑으면서 연결된 간선 끊기
		StringBuilder sb = new StringBuilder();
		while(!queue.isEmpty()) {
			int now = queue.poll();
			
			sb.append(now + " ");
			
			int size = edge[now].size();
			for(int i=0; i<size; i++) {
				// 연결된 간선 찾기
				int target = (int)edge[now].get(i);
				
				// 해당 간선 끊기
				indegree[target]-=1;
				if(indegree[target]==0)
					queue.add(target);
			}
		}
		
		System.out.println(sb.toString());
	}
}