[BOJ]2252. 줄세우기 (python)

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

2252번: 줄 세우기

 

문제

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

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

입력

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

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

출력

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

 

 

풀이

1. dfs를 이용

2. 위상정렬을 이용

 

두가지 방법이 있다.

 

dfs

1. dfs 탐색을 하고, 출력을 반대로 한다. 즉, 1 - 2 - 3 - 4 이렇게 연결되면, dfs를 이용해 탐색하면 4에 도달한다.
그러면 4 - 3 - 2 - 1 순으로 탐색하게 되는데, 이를 반대로 출력하면 위상정렬이 된다.

 

위상정렬

1. 2차원 배열을 저장하고, 간 Node별로 진입 간선(?)의 수를 count한다.
2. indegree(진입간선)이 0인 경우 queue에 넣고, 연결된 간선을 다 제거한 후, 제거된 간선과 연결된 Node들의 indegree가 0이라면 다시 queue에 집어 넣는다!

 

코드

비효율적인 dfs 방식 (dfs가 비효율적인게 아닌, 제가 푼 방식을 말하는 겁니다!)

import sys

N, M = map(int, sys.stdin.readline().strip().split())

height_list = [[] for _ in range(N + 1)]

# 2차원 배열에  a < b임을 저장하기
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    height_list[a].append(b)



visited = [0] * (N + 1)

sorting_box = []
# 마지막 줄이 핵심! 다 방문하고 나서 list에 추가해준다. 재귀이기 때문에, 가장 마지막 호출된 함수가 먼저 담긴다! 1 2 3호출하면 [3, 2, 1]이 담긴다
def dfs(x):
    visited[x] = 1

    for target in height_list[x]:
        if visited[target] == 0:
            visited[target] = 1
            dfs(target)
    sorting_box.append(x)


for i in range(N + 1):
    if visited[i] == 0 and len(height_list[i]):
        dfs(i)

# 아무것도 연결되지 않은 노드를 추가하기 위함. (굉장히 비효율적인듯)
for i in range(1, N + 1):
    if len(height_list[i]) == 0 and i not in sorting_box:
        sorting_box.append(i)

print(*sorting_box[::-1])

 

indegree를 이용한 방식! (위상정렬을 이용)

 

import sys
import collections


N, M = map(int, sys.stdin.readline().strip().split())

height_list = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
queue = collections.deque()


for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    height_list[a].append(b)
    indegree[b] += 1

for i in range(1, N + 1):
    if indegree[i] == 0:
        queue.append(i)


sorting_box = []
while queue:
    target = queue.popleft()
    sorting_box.append(target)
    for i in height_list[target]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)
print(*sorting_box)