#24479. 알고리즘 수업 - 깊이 우선 탐색 1 (#24479. 알고리즘 수업 - 깊이우선탐색1)와 (#24480. 알고리즘 수업 - 깊이 우선 탐색 2 (#24480. 알고리즘 수업 - 깊이우선탐색2)은 DFS로 탐색하는 문제였다면 이번 문제는 BFS로 탐색하는 문제이다.
BFS의 의사코드를 토대로 ‘큐’로 접근해보도록 한다.
bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점
for each v ∈ V - {R}
visited[v] <- NO;
visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.
enqueue(Q, R); # 큐 맨 뒤에 시작 정점 R을 추가한다.
while (Q ≠ ∅) {
u <- dequeue(Q); # 큐 맨 앞쪽의 요소를 삭제한다.
for each v ∈ E(u) # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
if (visited[v] = NO) then {
visited[v] <- YES; # 정점 v를 방문 했다고 표시한다.
enqueue(Q, v); # 큐 맨 뒤에 정점 v를 추가한다.
}
}
}
또한 #24444. 알고리즘 수업 - 너비 우선 탐색 1 문제와는 다르게 이 문제에서는 인접 정점을 내림차순으로 방문한다고 하였다 이 점에 유의해서 문제 풀이 해보도록 한다.
이전 문제에서의 내용과 거의 유사하고 bfs 함수부분의 코드만 다르다.
import sys
from collections import deque
input = sys.stdin.readline
# BFS 함수
def bfs(v, graph, visited):
queue = deque([v])
order = 1
while queue: # 큐가 빌 때까지 반복
# 큐에서 원소를 하나 뽑아 node에 대입한다.
node = queue.popleft()
if visited[node] == 0:
visited[node] = order # 방문하면 순서 넣기
order += 1
graph[node].sort(reverse=True) # 내림차순으로 인접노드 방문하기 위해 정렬
for u in graph[node]:
if visited[u] == 0: # 인접 노드 중에서 방문 안 한 노드면 bfs 탐색
queue.append(u)
# 초기화
n, m, r = map(int, input().strip().split()) # n: 정점의 수, m: 간선의 수, r: 시작 정점
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
order = 1
# 그래프 연결
for _ in range(m):
u, v = map(int, input().strip().split())
graph[u].append(v)
graph[v].append(u)
bfs(r, graph, visited)
# 해당노드를 몇 번째로 방문했는지 출력
for i in range(1, len(visited)):
print(visited[i])
deque 라이브러리를 import하여 queue를 deque로 형변환한다.queue에 시작 노드를 enqueue한다.order 변수를 1로 초기화한다.dequeue 해서 node에 저장한다.order)를 visited 리스트에 저장하고, 다음 순서로 넘어간다.n, 간선의 수 m, 시작정점 r을 입력받고, 빈 그래프인 graph 리스트를 초기화한다.visited 리스트는 1부터 n까지의 노드를 모두 0으로 초기화한다. 문제에서 방문할 수 없는 노드면 0을 출력하라고 했으므로 0으로 설정한다.