[백준] 24479 : 알고리즘 수업 - 깊이 우선 탐색 1,2 (파이썬)

 

문제

https://www.acmicpc.net/problem/24479

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

---

코드

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

def dfs(c):
    global cnt # 참조변수가 아니므로 함수밖에서 가져다 쓰기 위해 전역변수 선언
    v[c] = cnt
    cnt += 1
    
    for i in adj[c]:
        if v[i] == 0:
            dfs(i)

N, M, R = map(int, input().split())
adj = deque([[] for _ in range(N+1)])

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

for lst in adj:
    lst.sort()
 
cnt = 1 # 노드 순서별로 몇번째로 방문했는지 확인
v = [0]*(N+1)
dfs(R)

for i in range(1,N+1): # 0번 노드는 없으므로 1번 노드부터
    print(v[i])

• 재귀 함수 사용시 필수 코드
  • import sys
    sys.setrecursionlimit(10**9)  => 파이썬의 기본 재귀 깊이 제한을 늘려줌 set / recursion / limit
• input = sys.stdin.readline
• v[노드번호]에  노드의 방문 순서대로 cnt변수를 += 1 해서 넣어줌
• 함수 밖 일반변수(주소참조 X)를 함수 안에서 사용하기 위해 global cnt 선언

---

깊이 우선 탐색문제 2

인접 정점을 내림차순 방문하면 되므로

for lst in adj:
    lst.sort(reverse=True)

인접 리스트를 정렬할 때 sort(reverse=True) 만 해주면 노드가 내림차순으로 저장되어 방문 가능