BFS(너비우선탐색) python으로 구현

Breadth First Search, BFS

오늘은 BFS를 알아보자

BFS는 트리나 그래프를 방문 또는 탐색하는 방법이다.

 

탐색 방법

1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.

그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다.

 

코드 구현

 

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때 까지 2번을 반복

 

bfs(그래프 탐색)

from collections import deque

def bfs (graph, start, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

bfs(graph, 1, visited)

 

bfs(2차원배열)

from collections import deque

def bfs (graph, visited):
    # 상하좌우 네 방향을 의미
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([(0,0)])
    # 현재 노드를 방문 처리
    visited[0][0] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        x,y = queue.popleft()
        # 탐색 순서 출력
        print(x,y, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in range(4):
            if not (visited[i]):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]):
                    if (nx, ny) not in visited and graph[nx][ny] == 'O':
                        visited[nx][ny] = True; #방문표시
                        queue.append((nx, ny))
                
graph = [
        ['O', 'O', 'O', 'O', 'O', 'X'],
        ['O', 'O', 'O', 'O', 'X', 'O'],
        ['O', 'O', 'O', 'X', 'O', 'O'],
        ['O', 'O', 'X', 'O', 'O', 'O'],
        ['X', 'O', 'O', 'O', 'O', 'O'],
    ]

# 노드별 방문 정보
visited = [[False] * len(graph[0]) for _ in range(len(graph))]

bfs(graph, visited)