[Python] 백준 24479번(DFS/BFS)

문제

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

입력

• 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
• 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

• 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

문제 풀이

• 각 노드의 방문 여부를 알 수 있는 visited 
• 출발노드에서 각 노드의 방문 순서를 알기 위해 또 다른 result 배열 생성
• 탐색하기 전 그래프 오름차순으로 정렬
• 방문되지 않은 노드인 경우 (visited[i] 값이 False)  재귀적으로 함수 호출하여 노드의 방문순서를 세고있는 cnt 값을 1 증가시킨 후, 방문처리 및 현재 방문 순서를 저장하고 있는 result[i] 에 cnt 값(현재 방문순서)를 넣어준다.
• result 배열의 값을 첫 번째 인덱스부터 차례대로 출력

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m, r = map(int,input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
cnt = 0
for _ in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

# 그래프 정렬
for i in graph:
    i.sort()

# 정점의 방문순서 출력
def dfs(v):
    global cnt
    cnt += 1
    visited[v] = True
    result[v] = cnt
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

dfs(r)
# result 출력
for i in range(1, n + 1):
    print(result[i])

sys.setrecursionlimit(10 ** 6) 를 작성하지 않을 경우 런타임 에러 발생

       -> 파이썬의 재귀깊이는 1000으로 얕기 때문에  재귀함수 문제 풀 때 무조건 작성하기