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

24480번 : 알고리즘 수업 - 깊이 우선 탐색 2

 

 

 

이번에도 pypy3 말고 python3에서 제출해야 합니다.

 

 

 

 

import sys
sys.setrecursionlimit(10**9)
n, m, r = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visited = [0] * (n+1)
visited[r] = 1
count = 1

def dfs(v):
    global count
    graph[v].sort(reverse=True)
    for i in graph[v]:
        if visited[i] == 0:
            count += 1
            visited[i] = count
            dfs(i)

dfs(r)

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

 

 

24479번 문제와 비슷한 문제다. 차이점은 깊이 우선 탐색을 할 때 숫자가 높은 노드부터 탐색한다는 것 입니다. 그래서 #1을 해줘서 내림차순으로 정렬해주면 문제의 정답이 됩니다.