알고리즘 수업 - 깊이 우선 탐색 2 - 24480번

알고리즘 수업 -깊이 우선 탐색 1과 비슷한 문제로 방문하는 정점을 내림차순으로 정렬해주면 된다.

정점을 정렬한 다음 reverse해주면 된다.

 

1. 방문하지 못하는 정점에 대해서 0으로 출력될 수 있도록 방문한 정점들을 리스트에 차례대로 추가해줘야한다.

2. 파이썬으로 재귀방법으로 풀 경우 런타임에러가 뜰 수 있다. 

파이썬의 재귀 깊이는 1000으로 매우 얕은 편이기 때문에 재귀의 제한을 풀어줘야한다. 

sys.setrecursionlimit(10 ** 6) 으로 제한을 적절하게 풀어줘야한다.

3. for 문으로 입력받을 때, readline을 사용하여 런타임을 줄여준다.

 

import sys
sys.setrecursionlimit(10 ** 6)

n, m, r = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

visited = [False]*(n+1)
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)


for i in range(n+1):
    graph[i].sort()
    graph[i].reverse()

check = []

def dfs(r):
    node = r
    visited[node] = True
    check.append(node)

    for i in graph[node]:
        if not visited[i]:
            dfs(i)
dfs(r)
ans = [0] * (n+1)
for i,j in enumerate(check):
    ans[j] = i+1

for i in range(1,n+1):
    print(ans[i])