[BOJ] Python 백준 알고리즘 수업 - 깊이 우선 탐색 1(24479)

 

 

 

전형적인 dfs 문제

방문을 오름차순으로 방문해야하기에 방문때마다 오름차순으로 정렬해줘야한다.

순차적으로 방문해 순서를 매기기 때문에 cnt를 외부에 두어 방문때마다 값을 증가시켜주며, visited 배열에 갱신해준다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(150000)

N, M, R = map(int,input().split())

visited = [0] * (N+1)
cnt = 1
s = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    s[x].append(y)
    s[y].append(x)
def dfs(v):
    global cnt
    visited[v] = cnt
    s[v].sort()
    for j in s[v]:
        if not visited[j]:
            cnt += 1
            dfs(j)



dfs(R)

for i in range(1,N+1):
    print(visited[i])

 

회고. 

계속 sys.setrecursionlimit(10**5)로 맞춰줬는데 부족하다고 나왔다,

 

 

확인해보니

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

 

라고 한다...

 

조건을 잘 파악해 재귀 깊이를 설정해줘야함

너무 많으면, overflow나고 너무 적으면 recursion 에러 남,,