🟩 [백준] [Python] 24444번_알고리즘 수업 - 너비 우선 탐색 1

문제

https://www.acmicpc.net/problem/24444

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

풀이

# 백준 24444번 문제 - 알고리즘 수업 - 너비 우선 탐색 1
from collections import deque
import sys
input = sys.stdin.readline
n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(n):
    q = deque()
    q.append(n)
    visited[n] = 1
    count = 1
    while q:
        v = q.popleft()
        graph[v].sort()
        for i in graph[v]:
            if not visited[i]:
                count += 1
                visited[i] = count
                q.append(i)

bfs(r)
for i in visited[1:]:
    print(i)

이전에 풀었던 너비 우선 탐색 2와 같은 유형이라 쉽게 풀 수 있었다. 

sys를 사용하여야 시간초과가 나지 않고 해결이 가능하다.