백준 24479 - 깊이 우선 탐색 1 (Python3)

코드

import sys
sys.setrecursionlimit(10**6)
n, m, r = map(int, input().split())

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

# 해당 노드의 방문 순서를 담을 리스트
node_seq = [0 for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 시간 초과를 방지하기 위해 입력을 받은 후 정렬 수행
for i in range(n+1):
    graph[i].sort()

# 방문 순서를 담을 변수
seq = 1

def dfs(graph, visited, r):
    global seq
    
    # 노드 방문 처리
    visited[r] = True
    
    # 값이 0 => 아직 방문한 적이 없음
    # seq 값을 넣어줌으로써 순서를 부여
    if node_seq[r] == 0:
        node_seq[r] = seq
        seq += 1 # 순서가 1씩 증가하므로 +1
    
    for i in graph[r]:
        if not visited[i]:
            # visited[i] = True
            dfs(graph, visited, i)

dfs(graph, visited, r)

for i in range(1, len(node_seq)):
    print(node_seq[i])

문제 해설

DFS 문제.

방문 순서를 묻는 문제이나, 방문하지 않는 경우 0을 출력하라는 부분 때문에 애를 먹었다. 결국 구글링을 통해 다른 분들은 어떤 방법으로 해결하였는지 참고하여 순서를 담을 별도의 리스트를 사용하는 방식으로 문제를 해결했다. 재귀 깊이 관련 에러가 발생하므로

import sys
sys.setrecursionlimit(10**6)

위의 코드로 재귀의 최대 깊이를 늘려줘야만 에러를 피할 수 있다.