[백준] 24484번 알고리즘 수업 - 깊이 우선 탐색 6

💡문제접근

• DFS 기본 코드 + 별도로 내림차순 정렬 수행
• 방문 여부와 방문 순서를 모두 고려

💡코드(메모리 : 71988KB, 시간 : 588ms)

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

N, M, R = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().strip().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(len(graph)):
    graph[i].sort(reverse=True)

visited = [-1] * (N+1)  # 방문 깊이 d
sequence = [0] * (N+1)  # 방문 순서 t

idx = 1
visited[R] = 0
def DFS(v):
    global idx
    sequence[v] = idx
    for i in graph[v]:
        if visited[i] == -1:
            idx += 1
            visited[i] = visited[v] + 1
            DFS(i)

DFS(R)
Sum = 0
for i in range(N+1):
    Sum += visited[i] * sequence[i]
print(Sum)

💡소요시간 : 7m