[24444번] 알고리즘 수업 - 너비 우선 탐색 1

백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

코드 풀이

• result 변수의 크기는 총 노드의 수로 만듭니다. 초기값은 0으로 넣습니다.
• 어떤 노드에 방문했다면 그 노드를 몇 번째로 방문했는지를 알기 위해 cnt를 도입합니다.
• 해당 노드를 방문했다면 result 변수의 해당 노드의 값을 cnt로 할당합니다.
• BFS 후 한 번도 방문하지 않은 노드는 자동으로 0의 값이 기록되어 있을 것입니다.

import sys
from collections import deque


def bfs(start):
    q = deque()
    visited[start] = 1
    q.append(start)
    cnt = 1
    result[start] = cnt
    while q:
        x = q.popleft()
        for i in graph[x]:
            if not visited[i]:
                cnt += 1
                visited[i] = 1
                q.append(i)
                result[i] = cnt


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

visited = [0] * (n + 1)
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)

for i in range(n+1):
    graph[i].sort()

result = [0] * (n + 1)
bfs(R)

for i in result[1:]:
    print(i)