문제

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

문제접근

처음에는 트리를 생각했다.
1번이 3번보다 앞에 있어야한다. -> 3번 아래 1번을 놓자.
하지만 문제가 있었다.
1 3
2 3
5 1
6 5
7 6
...
처럼 깊이가 깊어지면 예를들어 7번 노드가 어디에 있는지 못 찾는 다는 것. 이진 트리면 대소 관계로라도 될텐데 이건 어떻게 해야 할지 모르겠다.

위상 정렬 접근법을 검색하고 DFS로 접근하는 방법을 알았다.

코드

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10**8)
input = stdin.readline

n, m = map(int, input().split())


def dfs(i):
    visited[i] = 1
    for j in g[i]:
        if visited[j]:
            continue
        dfs(j)
    ans.append(i)


visited = [0 for i in range(n + 1)]
g = [[] for i in range(n + 1)]

ans = []
for _ in range(m):
    a, b = map(int, input().split())
    g[b].append(a)
for i in range(1, n + 1):
    if visited[i]:
        continue
    dfs(i)
for i in ans:
    print(i, end=" ")

복잡도 분석

노드 갯수 N(1 ≤ N ≤ 32,000)
간선 갯수 M(1 ≤ M ≤ 100,000)

시간 복잡도

DFS를 연결리스트로 구현 => O(n+m)
채점결과 : 180ms

공간 복잡도

방문여부 리스트 O(n)
재귀 스택 최대 깊이 O(n)
간선 2차원 리스트 O(m)
총 O(n+m)
채점 결과 : 40268KB

학습포인트

DFS 말고 위상정렬을 푸는 다른 방법도 적용해보기.
setrecursionlimit 설정 까먹지 말기.
노드가 1부터 n까지니 리스트 범위 잘 보기.