[TIL] 250409 - BFS

바킹독님의 BFS 강의를 참고해 파이썬 버전으로 정리했습니다. 원래 깃허브에 private으로 정리를 했는데, 앞으로는 티스토리에 정리를 해보려 합니다. 

BFS : Queue(큐)로 구현

BFS(Breadth-First Search:너비 우선 탐색)

1. BFS란?

• BFS는 그래프 탐색 알고리즘 중 하나로, 너비(횡적) 방향으로 탐색을 진행하는 방식임
• 가장 가까운 노드부터 차례로 탐색한 후, 다음 단계의 노드를 탐색함
• 최단 경로 탐색에 적합하며, 동일 레벨의 노드를 먼저 탐색하는 특징을 가짐

2. BFS 동작 과정

1. 시작 노드를 큐에 저장
2. 큐의 맨 앞 값을 꺼냄 (Dequeue)
3. 현재 노드에서 수행해야 할 연산 수행
4. 현재 노드와 연결된 인접 노드 중 방문하지 않은 노드를 큐에 저장
5. 탐색이 끝난 노드는 큐에서 제거
6. 큐가 빌 때까지 2~5 과정 반복

3. BFS와 큐(Queue)

• BFS는 탐색 순서를 유지하기 위해 큐(Queue)를 사용함
• 큐는 선입선출(First In First Out, FIFO) 구조를 가지므로, 먼저 발견한 노드를 먼저 탐색하는 BFS와 궁합이 잘 맞음

4. BFS vs DFS 차이점

탐색 방식	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 순서	가까운 노드부터 탐색	깊은 노드부터 탐색
자료구조	큐 (Queue)	스택 (Stack) 또는 재귀
특징	최단 경로 보장, 레벨 탐색	경로의 깊이 우선 탐색
적용 사례	최단 거리 탐색, 네트워크 탐색	경로 찾기, 퍼즐 문제 해결

 

• 파이썬으로 BFS를 작성할 때도 어느 정도 표준적인 구조가 있습니다. 특히 코딩 테스트 (예: 삼성 A형 등)를 대비할 때는 이 구조를 완전히 외워서 언제든지 빠르게 구현할 수 있도록 숙달해 두는 것이 좋습니다.

board = [
    [0, 0, 0, 0],  # 0번째 행 (x = 0)
    [0, 0, 0, 0],  # 1번째 행 (x = 1)
    [0, 0, 0, 0],  # 2번째 행 (x = 2)
    ...
]

board를 시각화하면
(0,0) (0,1) (0,2) (0,3)  → y 증가 = 오른쪽
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
↓
x 증가 = 아래
x+1 → 아래로 한 칸 내려감
y+1 → 오른쪽으로 한 칸 이동

 

BFS 구현에서 할 수 있는 실수들

1. 시작점에 방문했다는 표시를 남기지 않음
2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남김
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못함

기본적인 BFS 틀

from collections import deque

# board는 탐색을 진행할 맵을 나타내는 2차원 리스트입니다.
# 0은 이동 가능한 칸, 1은 이동 불가능한 칸으로 생각하면 됩니다.
board = [[0]*502 for _ in range(502)]
vis = [[False]*502 for _ in range(502)]
# vis는 각 칸의 방문 여부를 나타내는 리스트입니다.

# dx와 dy는 상하좌우 이동을 편리하게 처리하기 위한 변수입니다.
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
    #아래,오른쪽,위,왼쪽 순서

# n과 m은 보드의 크기를 나타냅니다. (행과 열 개수)
n, m = 7, 10  # 예시 값이며 실제 문제에 맞게 조정해야 합니다.

def bfs():
    # 파이썬에서의 큐는 collections 모듈의 deque를 사용하는 것이 효율적입니다.
    Q = deque()
    # 시작점인 (0, 0)을 큐에 넣고 방문 표시합니다.
    Q.append((0, 0))
    vis[0][0] = True
    
    # 큐가 빌 때까지 탐색을 반복합니다.
    while Q:
        # 현재 탐색할 칸을 큐에서 꺼냅니다.
        cur_x, cur_y = Q.popleft()
        # 현재 방문한 칸의 좌표를 출력합니다 (방문 순서를 확인하기 위한 용도)
        print(f"({cur_x}, {cur_y}) -> ", end='')

        # 상하좌우 네 방향에 대해 탐색합니다.
        for dir in range(4):
            nx = cur_x + dx[dir]
            ny = cur_y + dy[dir]

            # 범위를 벗어난 경우 제외
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            # 이미 방문했거나 지나갈 수 없는 칸인 경우 제외.
            # 지금 코드에서는 board를 다 0으로 채웠지만, 나중에 1로 채워진 칸을 벽으로 처리할 수도 있음
            if vis[nx][ny] or board[nx][ny] != 0:
                continue

            vis[nx][ny] = True # 방문 표시
            Q.append((nx, ny)) # 다음 탐색을 위해 큐에 넣어줌

bfs()

출력

(0, 0) -> (1, 0) -> (0, 1) -> (2, 0) -> (1, 1) -> (0, 2) -> (3, 0) -> (2, 1) -> (1, 2) -> (0, 3) -> (4, 0) -> (3, 1) -> (2, 2) -> (1, 3) -> (0, 4) -> (5, 0) -> (4, 1) -> (3, 2) -> (2, 3) -> (1, 4) -> (0, 5) -> (6, 0) -> (5, 1) -> (4, 2) -> (3, 3) -> (2, 4) -> (1, 5) -> (0, 6) -> (6, 1) -> (5, 2) -> (4, 3) -> (3, 4) -> (2, 5) -> (1, 6) -> (0, 7) -> (6, 2) -> (5, 3) -> (4, 4) -> (3, 5) -> (2, 6) -> (1, 7) -> (0, 8) -> (6, 3) -> (5, 4) -> (4, 5) -> (3, 6) -> (2, 7) -> (1, 8) -> (0, 9) -> (6, 4) -> (5, 5) -> (4, 6) -> (3, 7) -> (2, 8) -> (1, 9) -> (6, 5) -> (5, 6) -> (4, 7) -> (3, 8) -> (2, 9) -> (6, 6) -> (5, 7) -> (4, 8) -> (3, 9) -> (6, 7) -> (5, 8) -> (4, 9) -> (6, 8) -> (5, 9) -> (6, 9) ->

 

 

BFS 를 연습해보기 좋은 문제들입니다.

백준 1926 그림

# 1926 그림림
from collections import deque
n,m = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

visited = [[False]*m for _ in range(n)]   

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

total_size = []
num = 0

for i in range(n):
    for j in range(m):
        if visited[i][j] == False and (board[i][j] == 1): 
            # 아직 방문 안한 상태면서 그림인 경우(1인 경우)
            # bfs 탐색의 첫 시발점으로
            Q = deque()
            Q.append((i,j))
            visited[i][j] = True
            size = 1 # 그림 넓이
            num += 1 # 그림 개수
            
            while Q:
                curr_x, curr_y = Q.popleft()
                
                # 범위 초과하지 않는 다음 위치 만들기
                for dir in range(4):
                    nx = curr_x + dx[dir]
                    ny = curr_y + dy[dir]
                
                    if nx <0 or nx >= n or ny <0 or ny >= m:
                        continue
                
                    if board[nx][ny] == 1 and visited[nx][ny] == False: 
                    # 그림 부분이고 거길 방문한적이 없으면
                        Q.append((nx,ny))
                        visited[nx][ny] = True # 방문했다고 체크
                        size += 1
                
            total_size.append(size)

print(num)
if num == 0:
    print(0)
else:
    print(max(total_size))

 

 

백준 2178 미로탐색

# 2178번 미로탐색
# bfs로 거리를 측정할 수 있음
from collections import deque

n,m = map(int, input().split())

board = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

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

Q = deque()
Q.append((0,0))
board[0][0] = 1

while Q:
    curr_x, curr_y = Q.popleft()
    visited[curr_x][curr_y] = True
    
    for i in range(4):
        nx = curr_x + dx[i]
        ny = curr_y + dy[i]
        
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        
        if board[nx][ny] == 0 or visited[nx][ny]==True:
            # 갈 수 없는 0이거나 방문한경우 
            continue
        
        board[nx][ny] = board[curr_x][curr_y] + 1
        visited[nx][ny] = True
        
        Q.append((nx,ny))
    
print(board[n-1][m-1])

• BFS를 이용하면 거리를 측정할 수 있다는걸 보여주는 문제입니다.
• board 에 지나가는 자리마다 지나온 거리를 기록해줘서 문제를 풀었습니다.

 

백준 7576 토마토

# 7576 토마토
from collections import deque

m,n = map(int, input().split())
# 익은 토마토(1), 안익은 토마토(0), 토마토 없음(-1)
# 모든 토마토가 익지는 못함 -> -1 출력 / 
# 처음부터 전부 다 익어 있으면(0이 하나도 없으면) -> 0 출력

# board를 만들때 1이 있는 위치를 먼저 뽑아두기
board = []
visited = [[False]*m for _ in range(n)]

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

# 익은 토마토의 위치
ripe_tomato = deque() 
# 처음부터 1인거 넣어서 시작. 평소 Q = deque()를 이걸로 대체

# 안익은 토마토(0) 개수 체크 -> 처음부터 하나도 없으면 바로 0 출력
unripe_tomate = 0

for i in range(n):
    append_list = list(map(int, input().split()))
    board.append(append_list)
    
    unripe_tomate += append_list.count(0)
    
    if append_list.count(1) != 0: # 익은 토마토가 있으면
        for ind, j in enumerate(append_list):
            if j == 1:
                ripe_tomato.append((i,ind))
                visited[i][ind] = True

# 처음부터 익을 토마토가 없으면 0출력
if unripe_tomate == 0:
    print(0)
else:
    while ripe_tomato:
        curr_x, curr_y = ripe_tomato.popleft()
        
        for i in range(4):
            nx = curr_x + dx[i]
            ny = curr_y + dy[i]

            if nx <0 or nx>=n or ny<0 or ny>=m:
                continue
            if visited[nx][ny] == True or board[nx][ny] == -1:  
                continue
            
            ripe_tomato.append((nx,ny))
            visited[nx][ny] = True
            board[nx][ny] = board[curr_x][curr_y] + 1

    count_zero = False
    max_num = 1
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                count_zero = True
                break
        if count_zero:
            break
        else:
            max_board = max(board[i])
            if max_board > max_num:
                max_num = max_board
    if count_zero:
        print(-1)
    elif max_num != 1:
        print(max_num-1)

 

백준 4179 불!

# 4179 불!
from collections import deque

R,C = map(int,input().split())
board = [list(input().strip()) for _ in range(R)]

F_time = [[-1]*C for _ in range(R)] # 불이 옮겨간 시간
J_time = [[-1]*C for _ in range(R)] # 지훈이가 옮겨간 시간

J_Q = deque()
F_Q = deque()
        
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 불의 전파가 되는 시간을 먼저 F_time에 기록하고
# 다음으로 지훈이의 위치를 보는데, 이때 지훈이가 도달하는 시간이 불이 도달한 시간보다 작아야만
# 지훈이가 갈 수 있는길
# 즉,불이 먼저 도달했다면 벽처럼 처리해주기

# 불과 지훈의 시작 위치 deque에 추가
for i in range(R):
    for j in range(C):
        if board[i][j] == 'J':
            J_Q.append((i,j))
            J_time[i][j] = 1
        elif board[i][j] == 'F':
            F_Q.append((i,j))
            F_time[i][j] = 1
# 불 도착 시간 기록
while F_Q:
    curr_x, curr_y = F_Q.popleft()
    
    for i in range(4):
        nx = curr_x + dx[i]
        ny = curr_y + dy[i]
        
        if nx<0 or nx>=R or ny<0 or ny>=C:
            continue
        elif board[nx][ny] == '#' or F_time[nx][ny] != -1:
            continue
        else:
            F_time[nx][ny] = F_time[curr_x][curr_y] + 1
            F_Q.append((nx,ny))

# 지훈이 
def solve():
    while J_Q:
        curr_x, curr_y = J_Q.popleft()
        
        for i in range(4):
            nx = curr_x + dx[i]
            ny = curr_y + dy[i]
            next_record = J_time[curr_x][curr_y] + 1
            
            if nx<0 or nx >= R or ny<0 or ny >= C:
                print(J_time[curr_x][curr_y])
                return
                
            if board[nx][ny] == '#' or J_time[nx][ny] != -1:
                continue
            # 불이 도착하지 않았거나, 지훈이가 더 빨리 도착하면 이동 가능
            if F_time[nx][ny] != -1 and next_record >= F_time[nx][ny]:
                continue
            J_time[nx][ny] = next_record
            J_Q.append((nx,ny))
    print('IMPOSSIBLE')
    
solve()

 

백준 1697 숨바꼭질

# 1697 숨바꼭질
def solve():
    from collections import deque
    a,b = map(int,input().split())
    limit = 200001
    board = [0] * limit
    Q = deque()
    
    board[a] = 1
    Q.append(a)
    
    while Q:
        curr_x = Q.popleft()
        
        if curr_x == b:
            print(board[curr_x]-1)
            return
        
        for nx in [curr_x-1,curr_x+1,curr_x*2]:
            # print(nx)
            if nx<0 or nx>= limit:
                continue
            if board[nx] > 0:
                continue
            # print(nx)
            board[nx] = board[curr_x] + 1  
            Q.append(nx)

solve()