[Python] 너비 우선 탐색 BFS

너비 우선 탐색

루트노드(혹은 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 방문해나가 가장 멀리 떨어진 정점을 나중에 방문하는 순회 방법
말그대로 넓게 탐색하는 방법 (방문한 노드를 기준으로 주변을 탐색해나가므로)
깊이 우선 탐색보다 조금 더 복잡함

1. 루트 노드를 큐에 넣고 방문처리한다.
2. 큐를 Deque 하고, Deque 한 노드의 방문하지 않은 모든 인접 노드를 큐에 넣고 방문 처리한다.
3. 2단계를 더 이상 수행할 수 없을 때 까지 (큐가 빌 때 까지) 반복한다.

💡 특징

• 거리에 따라 단계별로 탐색하므로 직관적이지 않은 면이 있음
• 그래프 탐색의 경우 어떤 노드를 방문했는지 반드시 검사해야 함 → 그렇지 않을 경우 무한 루프에 빠질 위험 있음
• 재귀적으로 동작하지 않음
• 방문한 노드를 차례로 저장한 후 꺼내는 큐(Queue)를 사용(선입선출의 원칙)
• 시간 복잡도는 O(N)의 시간 소요 (단, 실제 수행 시간은 DFS > BFS)

사용 예시

• 주로 최단 경로 문제 해결에 사용(두 정점간의 최단 경로 찾기 등)
• cheney's algorithm나 copying garbage collection 등을 해결하는데 사용

def BFS(graph, S): # BFS 정의
    visited = [False]*(len(graph)+1) # 방문 처리를 위해 생성
    queue = []
    queue.append(S)
    visited[S] = True # 현재 노드 방문처리
    while queue :
        a = queue.pop(0) #큐에 순차적으로 삽입
        print(a, end = ' ')
        for i in graph[a]: #방문하지 않은 인접 노드들을 큐에 삽입
            if not visited[i] : 
                queue.append(i)
                visited[a] = True

graph = [[],[2,3,4],[],[],[5,6],[],[]]
BFS(graph,1)

# 출력결과 : 1, 2, 3, 4, 5, 6

# 방문한 노드까지의 길이를 확인하는 소스코드(예시 미로)

#시작 지점이 2, 종점이 3인 미로를 종점까지의 거리 탐색하는 코드
def bfs(a, b):
    visited = [[0] * N for _ in range(N)]
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 상하좌우
    queue = []
    queue.append([a, b])  # 큐에 초기값 지정
    visited[a][b] = 1  # 초기값 1
    while queue:
        y, x = queue.pop(0)
        if maze[y][x] == 3:
            return visited[y][x] - 2  # 도착지점 기준 시작값 1과 끝값 1을 뺴줘야함
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            # 범위 밖을 벗어나지 않으면서 1이 아니고, 방문하지 않았을 경우
            if 0 <= ny < N and 0 <= nx < N and maze[ny][nx] != 1 and visited[ny][nx] == 0:
                visited[ny][nx] = visited[y][x] + 1
                queue.append([ny, nx])
    return 0

N = 5
maze = [[1,1,2,1,1],[1,1,0,1,1],[1,1,0,1,1],[1,1,0,1,1],[1,1,0,0,3]]
print(bfs(0,2))

# 출력 결과 6

출처
https://edder773.tistory.com/35
https://hudi.blog/dfs-bfs/