알고리즘 수업 - 깊이 우선 탐색 1 - 24479번

DFS를 해결해야하는 문제이다.

정점 개수, 간선 개수, 시작지점을 입력받고 그래프를 입력받는다.

i 번째에는 정점 i 의 방문 순서를 출력하고, 방문하지 못하는 정점은 0을 출력해야한다.

 

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()

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])