[Baekjoon]백준 24444 알고리즘 수업 - 너비 우선 탐색 1(실버 2) - Python

문제설명 1

문제설명 2

문제를 살펴보면 이전 단계에서 풀었던 dfs(깊이 우선 탐색)이 아니라 bfs(너비 우선 탐색)로 해결해야하는 문제이다

dfs는 한 노드에서 가능한 깊이까지 내려간 뒤 더이상 내려갈 수 없다면 한 단계씩 돌아오는 탐색방법이며

bfs는 한 노드에서 인접한 노드들을 모두 방문한 뒤 그 다음 단계로 넘어가 점차 멀리 있는 노드를 방문하는 방법이다

 

그래서 이전에 제출하였던 코드(24479-python)를 일부 수정하여 코드를 작성하였다

우선 덱을 사용하기 위해 from collections import deque를 사용하였다

이후 문제에서 주어진 입력들을 입력받고 해당 정보를 바탕으로 graph에 간선 정보를 입력을 해주었다

문제에서 인접정점은 오름차순으로 방문한다고 주어졌기 때문에 graph를 sort()로 정렬해주어야한다

 

이제부터가 핵심인데, queue를 생성하고  시작 노드를 첫번째 방문으로 기록한다

이후 큐에서 노드를 꺼낸후 꺼낸 노드의 이웃 노드를 탐색하며 아직 방문하지 않은 노드일 경우 cnt를 1 증가시키면서

방문 순서를 기록해준다 그리고 해당 노드를 queue.append()를 통해 다음 단계에서 탐색할 준비를 해준다

 

마지막으로 for문을 통해 각 노드의 방문 순서를 출력해주면 코드가 완성된다

import sys
input = sys.stdin.readline
from collections import deque

def bfs(start):
    global cnt
    queue = deque([start])
    visited[start] = cnt

    while queue:
        cur = queue.popleft()
        for neighbor in graph[cur]:
            if visited[neighbor] == 0:
                cnt += 1
                visited[neighbor] = cnt
                queue.append(neighbor)

vertex, edge, starting = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
visited = [0] * (vertex+1)
cnt = 1

for _ in range(edge):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()
    
bfs(starting)

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