백준 2252번 : 줄 세우기 in Python

2252번: 줄 세우기

 

www.acmicpc.net

이 문제는 키를 비교한 두 학생의 번호 쌍들이 주어졌을 때 학생들을 키 순서대로 세우는 문제이다.

구체젹인 예로 1 3이라는 번호 쌍이 주어진 경우 학생 1이 학생 3보다 앞에 서야 한다. 즉, 학생 1과 학생 3 사이에는 어떤 학생이 와도 상관이 없으나 학생 1이 학생 3보다는 반드시 앞에 있어야 한다는 의미이다.

이러한 문제를 해결하기 위해서는 위상 정렬을 알아야 한다. 위상 정렬이란 directed acyclic 그래프(각 간선의 방향이 존재하고 사이클이 없는 그래프)에서 임의의 정점을 방문하기 위해 그 정점으로의 간선을 모두 방문해야 한다는 조건이 붙은 경우의 그래프 탐색 방법을 말한다. 

위 문제의 경우를 예로 들어보자. 만약 어떤 학생 1이 학생 2, ... , 학생 n보다 더 뒤에 있다는 조건이 있는 경우 이를 그래프에서 간선 (2, 1), (3, 1), ... , (n, 1)에 대응시키고 해당 간선들을 모두 방문한 이후에 정점 1을 방문할 수 있다는 조건으로 해석할 수 있다. 

그렇다면 위상 정렬은 어떤 방법으로 해결할 수 있을까? 우선 모든 정점에 대해 DFS 함수를 호출한다. 그러면 재귀적으로 호출하는 경우를 포함해 모든 정점에 대해 한 번씩 DFS 함수를 실행하게 되는데, 이때 DFS 함수를 종료하기 직전에 위상 정렬의 결과를 저장할 배열 top_sort에 정점을 저장한다. 이 결과 나온 top_sort는 그래프 내 모든 정점을 하나씩 가지고 있는데, 이 정점의 순서는 위상 정렬의 결과의 역순이 된다. 그러므로 top_sort를 뒤집으면 위상 정렬의 결과를 얻게 된다.

위 내용을 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
# 위상 정렬의 결과를 저장하는 배열
top_sort = []
visited = [False for _ in range(N+1)]
def DFS(u):
    if visited[u]: return
    visited[u] = True
    for v in graph[u]:
        if not visited[v]:
            DFS(v)
    # DFS 함수를 종료하기 직전에 top_sort에 인자로 주어진 정점을 저장한다.
    top_sort.append(u)
for i in range(1, N+1):
    DFS(i)
# 각 정점에 대해 DFS 함수를 실행하면 top_sort에는 위상 정렬의 역순이 저장된다.
# 그러므로 이를 뒤집어 위상 정렬의 결과를 얻는다.
top_sort.reverse()
print(" ".join(list(map(str, top_sort))))