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

📚 문제

입력

출력

예제 입력

5 5 1
1 4
1 2
2 3
2 4
3 4

예제 출력

1
4
3
2
0

🧑🏻‍💻 풀이 과정

• 입력받은 graph로 dfs를 호출하자.
• 방문한 v에 대해서는 visited[v]를 True로 변경하고, 방문 순서를 answer[v]에 저장하자. (visited[4] = 2, visited[3] = 3, visited[2] = 4)
• 방문 순서는 내림차순이므로, graph를 내림차순 정렬하자.
• graph[v]의 노드를 반복하며, 방문하지 않은 노드를 발견하면, cnt를 1 증가 시키고, 해당 노드를 재귀 호출하자.
• 재귀호출이 끝나면, answer에 저장된 값을 반복하면서 출력하자.

import sys

sys.setrecursionlimit(10 ** 8)


def dfs(v):
    global cnt
    visited[v] = True

    # 4번은 2번째 방문, 3번은 3번째 방문, 2번은 4번째 방문
    # 카운트는 1씩 증가하는데.. 2번째일 때, 4번을 방문하므로, answer[4] = 2와 같다.
    answer[v] = cnt
    # 내림차순 정렬
    graph[v].sort(reverse=True)
    for i in graph[v]:
        if not visited[i]:
            cnt += 1
            dfs(i)


n, m, r = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
answer = [0] * (n + 1)
cnt = 1

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

dfs(r)

for val in answer[1:]:
    print(val)