[백준] 24447번 알고리즘 수업 - 너비 우선 탐색 4

💡문제접근

• BFS 기본 코드 + 별도로 오름차순 정렬 수행
• 노드의 방문 깊이와 노드의 방문 여부를 둘 다 고려해야함

💡코드(메모리 : 59416KB, 시간 : 560ms)

from collections import deque
import sys
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()

# 노드의 깊이
visited = [-1] * (N+1)
# 노드의 방문 순서 → idx로 판별
sequence = [0] * (N+1)
idx = 1

def BFS(x):
    global idx
    queue = deque()
    queue.append(x)
    visited[x] = 0      # 시작 정점의 깊이는 0, 방문 되지 않은 노드의 깊이는 -1
    sequence[x] = 1     # 시작 정점의 방문 순서는 1, 방문할 수 없는 노드는 0
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if visited[i] == -1:
                idx += 1
                visited[i] = visited[v] + 1
                sequence[i] = idx
                queue.append(i)

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

💡소요시간 : 9m