[APS] 7. BFS (너비 우선탐색)

1. DFS vs BFS

• DFS : 탐색 시작점을 기준으로 갈 수 있는 곳까지 방문한 후에, 더이상 갈 수 없으면 마지막으로 방문했던 곳으로 되돌아가서 다시 탐색을 진행하는 방식 ⇒ ‘스택’ 을 활용한다.

• BFS : 탐색 시작점의 인접한 정점을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 ⇒ ‘큐’ 를 활용한다.

2. 코드로 구현해보기

• 인접행렬을 구하는 것은 DFS 를 참고한다. (https://mummur.tistory.com/37)

• 기본적인 흐름은 다음과 같다.

• 참고로 백준에서는 그냥 list로 진행하면 타임에러가 났다. deque로 진행해야 time error가 나지 않는다.

# 준비물 : 인접행렬, 방문했는지 기록할 visited, 방문할 곳을 담은 queue.
# bfs
queue = deque()
visited_2 = [0]*(n+1)

visited_2[v] = 1
queue.append(v)
while queue:
    now_j = queue.popleft()
    print(now_j, end=" ")
    for j in range(1, n+1):
        if arr[now_j][j] == 1 and visited_2[j] == 0:
            queue.append(j)
            visited_2[j] = 1

Uploaded by N2T