[Python] BFS(Breadth-First Search) / 너비우선탐색

구현

1. 인접리스트로 표현된 그래프 BFS

from collections import deque


def bfs(n):
    q = deque()
    q.append(n)

    visited = [False] * 9

    while q:
        n = q.popleft()
        print(n, end=' ')

        for i in graph[n]:
            if not visited[i]:
                q.append(i)
                visited[i] = True


graph = [  # 각 노드가 연결된 정보를 2차원 리스트로 표현
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

 

활용

1. 2차원 리스트에서 출발 노드와 목표 노드 사이 최단 거리 구하기

# 5 X 5 배열
# start = (0, 0), end = (3, 4)
# 상하좌우 1칸씩 이동 가능

from collections import deque


def bfs(start, end):
    q = deque()
    q.append(start)  # 시작 노드

    visited = [[0 for _ in range(5)] for _ in range(5)]  # 방문 처리 + 거리
    x, y = start
    visited[x][y] = 1  # 시작 노드 방문 처리

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 5 and 0 <= ny < 5:
                if visited[nx][ny] == 0:  # 첫 방문
                    if (nx, ny) == end:  # 목표 노드와 동일한가?
                        return visited[x][y]

                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))  # 다음에 방문할 노드로 등록

    return -1  # start == end 인 경우 or 목표 노드의 범위가 옳지 않은 경우

 

---

장점

• 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

단점

• DFS보다 많은 메모리를 사용한다.