BFS with python

chanloper·2024년 7월 19일

자료구조

목록 보기

9/10

🔦 BFS와 DFS의 차이점

DFS는 탐색하는 원소를 최대한 깊게 따라가야 합니다.
이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
"가장 마지막에 넣은 노드"를 꺼내서 탐색하면 됩니다 - > 그래서 스택(Stack)을 사용
BFS는 현재 인접한 노드를 먼저 방문해야 합니다.
인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다. "가장 처음에 넣은 노드" -> 큐(Queue)를 사용

🔎 DFS가 깊이 우선 탐색이라면 BFS는 너비 우선 탐색이다.

구현 방법
1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited에 추가합니다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가합니다.
4. 2부터 반복합니다.
5. 큐가 비면 탐색을 종료합니다.

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

큐를 다시 기억하자 💡

https://velog.io/@chanloper/%ED%81%90Queue

큐를 이용한 BFS 구현

def bfs_queue(start):
    visited = [start] # 방문한 노드를 기록하는 리스트, 시작 노드로 설정(초기화)
    q = deque([start]) # 큐(queue), 시작 노드로 초기화된 dequq 객체 생성

    while q: # 큐에 방문할 노드가 남아 있는 동안 반복
        node = q.popleft() # 큐의 왼쪽에서 노드를 하나 꺼냄 ( 가장 오래된 노드 )

        for adj in graph[node]: # 현재 노드의 인정 노드들을 순회
            if adj not in visited: # 인접 노드가 방문되지 않았다면
                q.append(adj) # 큐에 인접 노드를 추가(append)하여 나중에 방문
                visited.append(adj) # 방문 처리

    return visited # 방문한 순서대로 노드들을 담은 visited 리스트 반환

assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

BFS는 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 그 인접한 노드들의 또 인접한 노드들을 방문하는 방식으로 동작합니다.
큐(Queue)를 이용한 BFS는 너비 우선 탐색의 특성상 같은 깊이에 있는 모든 노드를 먼저 방문하므로, 최단 경로 탐색등에 유용합니다.
deque 객체를 사용하여 큐를 구현하면 왼쪽에서 노드를 꺼내고 오른쪽에 노드를 추가하는 연산을 효율적으로 수행할 수 있습니다.

BFS로 섬의 개수 찾기
체감 난이도 : ⭐️⭐️⭐️☆☆

from collections import deque

def island_bfs(grid):
    # 상, 하, 좌, 우 방향을 나타내는 배열
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    # 그리드의 행과 열 길이
    rows, cols = len(grid), len(grid[0])

    # 섬의 개수를 세는 변수 'cnt'
    cnt = 0

    # 그리드의 각 셀을 하나씩 탐색
    for row in range(rows):
        for col in range(cols):
            # 현재 셀이 육지('1')가 아니면 건너뜀
            if grid[row][col] != '1':
                continue

            # 새로운 섬을 발견, 섬 개수를 증가시킴 (cnt+=1)
            cnt += 1
            q = deque([row,col]) # 시작점을 큐에 추가하여 초기화

            while q:
                x, y = q.popleft() # 큐에서 하나의 좌표를 꺼냄
                for i in range(4): # 상하좌우 방향에 대해 탐색
                    nx = x + dx[i] # 새로운 x 좌표 계산
                    ny = y + dy[i] # 새로운 y 좌표 계산
                    # 새로운 좌표가 그리드 범위를 벗어나거나 육지가 아니면 건너뜀
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue

                    grid[nx][ny] = '0' # 방문한 육지를 '0'으로 표시하여 방문 처리
                    q.append((nx,ny)) # 새로운 좌표를 큐에 추가하여 BFS 계속 진행

            # 한번의 BFS 탐색이 끝나면 해당 섬의 탐색을 완료하고 다음 셀로 이동
            
            return cnt # 섬의 개수를 반환