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

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

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

이 문제는 https://www.acmicpc.net/problem/24479 문제와 매우 유사하다. 24479번은 DFS였다면 24444번은 BFS로 해결해주면 된다. 

deque를 사용하여 BFS를 위한 큐를 만들었고, Q 안에 값이 없을 때까지(while 문을 통해) BFS를 실행하였다.

popleft를 사용하여 큐에 쌓인 값들을 순서대로 처리해주었다. 

다른 로직은 위의 문제와 유사하다.

# 알고리즘 수업 - 너비 우선 탐색 1
import sys
from collections import deque
input = sys.stdin.readline

def bfs(maps, visited, R):
    global ans
    Q = deque()
    Q.append(R)
    visited[R] = ans
    while Q:
        x = Q.popleft()
        for i in maps[x]:
            if visited[i] == 0:
                Q.append(i)
                ans += 1
                visited[i] = ans
                
N, M, R = map(int, input().split())
maps = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
ans = 1

for _ in range(M):
    a, b = map(int, input().split())
    maps[a].append(b)
    maps[b].append(a)

for i in range(1, N+1):
    maps[i].sort()

bfs(maps, visited, R)

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

성공!