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

에 정점 v를 추가한다.
}
}
}

##### 입력

첫째 줄에 정점의 수 *N* (5 ≤ *N* ≤ 100,000), 간선의 수 *M* (1 ≤ *M* ≤ 200,000), 시작 정점 *R* (1 ≤ *R* ≤ *N*)이 주어진다.

다음 *M*개 줄에 간선 정보 `*u* *v*`가 주어지며 정점 *u*와 정점 *v*의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ *u* < *v* ≤ *N*, *u* ≠ *v*) 모든 간선의 (*u*, *v*) 쌍의 값은 서로 다르다.

##### 출력

첫째 줄에 모든 노드에 대한 *di* × *ti* 값의 합을 출력한다.

##### 예제 입력 1

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

##### 예제 출력 1

13

> ### 제출 답안

```python
from collections import deque
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [-1] * (n + 1)
cnt = [0] * (n + 1)
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


def bfs(start):
    q = deque([(start, 1)])
    visited[start] = 0 * 1
    idx = 2
    answer = 0
    while q:
        node, cnt = q.popleft()
        for i in sorted(graph[node]):
            if visited[i] == -1:
                visited[i] = cnt * idx
                answer += visited[i]
                idx += 1
                q.append((i, cnt + 1))
    return answer


answer = bfs(r)
print(answer)