2252번. 줄 세우기 | 위상정렬

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

2252번: 줄 세우기

 

포인트

- 줄 세우기 문제

 

조건

- 일부 두 학생 비교

 

예제

총 3명이고, 키를 비교한 횟수는 2번이다.

첫 번째는 1번 학생이 3번보다 앞에 있어야한다.

두 번째는 2번 학생이 3번보다 앞에 있어야한다.

 

이걸 유추해봤을 때,

1, 2번은 무조건 3번보다 앞에 있어야한다.

하지만 1번이 2번보다 앞에 있어야하는 경우는 없다. 

그러므로 1,2,3 또는 2,1,3이다.

 

총 4명이고, 키를 비교한 횟수는 2번이다.

첫 번째는 4번이 2번보다 앞에 있어야한다.

두 번째는 3번이 1번보다 앞에 있어야한다.

 

이걸 유추해봤을 때,

4 2 3 1

또는 

3 4 2 1 등이 있을 수 있다.

 

이것은 정답이 여러개 발생할 수 있다.

N은 32만개가 가능하고, M은 10만개가 가능하다.

 

A가 B보다 커야한다는 조건이 있는 상태에서 정렬을 해야한다.

이것은 위상 정렬 알고리즘으로 해결할 수 있다. 

위상 정렬이란, 간단하게 "순서가 있는 일을 순서에 맞게 나열"하는 것이다. 즉, 방향이 존재한다.

 

 

예제 1을 보자.

1, 2번은 조건이 없으니까 비교할 수가 없다. 

그래서 1, 2번은 같은 키라고도 볼 수 있는 것.

1 

     ->   3

2    

대략 이런식으로 나타낼 수 있겠다. 잘 보니 트리처럼 생겼다.

1, 2는 진입차수가 0이라 할 수 있고, 3은 진입차수가 1이다. 

우리는 진입차수가 0부터 1, 2, .. 순서대로 출력 할 수 있게 할 것이다.

 

 

 

# 파이썬 인터프리터를 제어할 수 있는 방법을 제공한다.
import sys 
# deque란? double-ended queue의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조
from collections import deque 

# input() 대신 sys.stdin.readline 사용하는 이유?
# 여러 줄을 입력 받을 때 input()으로 받으면 시간초과가 발생할 수 있다.
input = sys.stdin.readline

# map()은 반복 가능한 객체에 대해 각각의 요소들을 지정된 함수로 처리한다.
n, m = map(int, input().split())

# n의 사이즈의 배열을 선언한다. 3이면 +1개해서 4까지
inDegree = [0] * (n + 1)
#print(len(inDegree)) 확인용

# 변수 _가 0, 1, 2, 3, 4, .. n 값을 가지고 반복 수행한다.
# 실제 사용되;지 않기 때문에 _ 을 사용한다.
graph = [[] for _ in range(n+1)]

# m번 줄을 세운다.
for _ in range(m):
    a, b = map(int, input().split())
    # a가 b보다 앞에 있어야한다. b는 degree 0+1로 1이다.
    # b가 도 나오면, b는 1+1로 2다
    # 1 3
    # 2 3 이 된다면 3의 degree는 2가 된다. 
    inDegree[b] += 1
 
    # a=[1,2,3] 에서 a.append("a") 하면, [1,2,3,'a'] 즉 뒤에 추가한다.
    # graph[1].append(2) 1 뒤에 2를 추가한다.
    # graph[1].append(3) 1 뒤에 2가 있는데 2 뒤에 3을 추가한다.
    graph[a].append(b)
    
queue = deque()
answer = []

# 1에서부터 n까지
for i in range(1, n+1):
    # 0번째인 친구들을 다 추가한다.
    if inDegree[i] == 0:
        queue.append(i)

while queue:
    # 큐의 왼쪽부터 뺀다
    current = queue.popleft()

    # 정답으로 추가하고
    answer.append(current)

    # 맨 왼쪽보다 뒤에 서있는 얘들을 분기한다
    for x in graph[current]:
        inDegree[x] -= 1

        # 같은 값이 나오면 안 되니까 하나씩 빼주고, 0이 되면 그 친구를 정답에 추가한다.
        if inDegree[x] == 0:
            queue.append(x)

print(*answer)