백준 24444 | BFS | 너비 우선 탐색 1 [파이썬 python]

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

 

코드

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 정점
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) # 방문 순서 저장. 0이면 방문 X

c = 1 # 순서
def bfs(graph, start, visited):
    global c
    queue = deque([start])
    visited[start] = c # 방문하면 순서 나타내기
    
    while queue:
        v = queue.popleft()
        for i in graph[v]: # 인접 노드 중
            if visited[i] == 0: # 방문하지 않은 노드 큐에 추가
                queue.append(i)
                c += 1 # 순서+1
                visited[i] = c

# m개의 연결된 간선 정보 입력받기
for i in range(m):
    a, b = (map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)
# print(graph)

for i in range(n+1): # 인접노드 정보 오름차순 정렬
    graph[i].sort()
# print(graph)

bfs(graph, r, visited)

for i in range(1, n+1):
    print(visited[i])

BFS로 해결하는 문제이다.

이전에 풀었던 DFS와 구조는 매우 비슷하기 때문에 BFS 함수 부분만 조금 수정해 주면 된다.

너비 우선 탐색에서는 큐(Queue)가 필요하기 때문에 deque를 import 해주고 queue를 만들어준다.

queue에는 시작할 노드를 먼저 담아주고, visited[start]를 c의 초기값인 1로 바꿔준다.

 

이제부터 인접 노드의 방문 여부를 확인한다.

queue에서 popleft()를 통해 노드를 하나 가져와 v에 저장한다.

queue가 비어있으면 while문은 종료된다. 즉 방문하지 않은 인접노드가 있으면 계속 반복되는 것이다.

 

방문하지 않은 인접노드가 무슨 말인지는 그 다음 for문을 보면 알 수 있다.

graph에서 v의 인접 노드 들을 가져와 하나씩 방문 여부를 확인한다.

방문하지 않은 노드(=0)이면 queue에 추가한다.

추가한 노드는 다음으로 방문해야할 노드이므로 방문순서 c를 +1 해주고 해당 노드의 visited에 방문 순서를 기록한다.

c+1을 for문 내부에서 어디에 작성하느냐에 따라 값이 달라지므로 과정을 잘 생각하며 작성해주어야 한다.

 

나머지 과정은 DFS 문제와 동일하므로 생략하겠다.