BOJ 2252 - 줄 세우기

문제

백준 온라인 저지 - 2252번

풀이 과정

위상 정렬 을 활용한 해법으로 해결할 수 있는 문제입니다.
다양한 방법이 있지만 DFS 를 활용해 위상 정렬 을 구현하는 것이 가장 간단해서 이 방법을 사용했습니다.

코드

import sys

n, m = list(map(int, sys.stdin.readline().split()))
adj = [[] for _ in range(n+1)]
for _ in range(m):
    frm, to = list(map(int, sys.stdin.readline().split()))
    adj[frm].append(to)


def dfs(here, visit, ans):
    visit[here] = 1

    for there in adj[here]:
        if not visit[there]:
            dfs(there, visit, ans)

    ans.append(here)


def solution():
    ans = []
    visit = [0 for _ in range(n+1)]
    for i in range(1, n+1):
        if not visit[i]:
            dfs(i, visit, ans)

    ans.reverse()
    return ' '.join(map(str, ans))


print(solution())