BFS(너비 우선 탐색) 알고리즘 (feat. 최단경로)
백준 2178번 문제(미로 탐색)를 풀던 중
아 이건 내가 아는 방법으로는 코드를 짜는 게 힘들겠다고 느꼈다...
임의의 행렬을 내가 입력하면 그게 미로가 되어서
1은 이동할 수 있는 칸, 0은 이동불가능한 칸으로 간주
내가 처음 생각한 풀이 방법은
N x M 형태의 행렬이므로
N, M = map(int, input().split()) # N은 행 M은 열
nums = [[0] * M for _ in range(N)]
for i in range(N):
for j in range(M):
nums[i][j] = int(input())이런 식으로 2차원 리스트로 만들어서 값을 저장한 뒤에
조건문과 반복문을 이용해서 (1,1)을 시작점으로 정하고
각 행과 열에서 1이 존재하는 걸 찾아서 어쩌고... 하려 했으나
무지막지하게 사이즈가 큰 행렬이 주어진다면 시간제한에 걸릴 것이고
제일 중요한 것은 목적지까지 이동하는데 지나야 하는 최소의 칸 수를 구하는 것인데
내가 생각한 것을 구현한다고 하더라도 최적의 경로를 계산하지 못할 것이라 생각이 들었다
따라서 이러한 상황에서 어떠한 방법을 사용해야 하는지 찾아보던 중
BFS(너비 우선 탐색)에 대해서 알게 되었다
얘가 뭐 하는 친구인지 설명해 보자면
최단 경로를 찾는 문제에 매우! 적합한 알고리즘이라고 한다
모든 가능한 경로를 한 층씩 탐색하므로, 먼저 도착하는 경로가 최단 경로가 된다고 한다
일단 이해하기 쉽게 주석이 포함된 코드를 봐보자
# GPT가 작성해준 코드
from collections import deque
# BFS 함수 정의
def bfs(matrix, N, M):
# 상하좌우 방향 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 큐 초기화 (시작점 (0, 0) 추가)
queue = deque([(0, 0)])
# BFS 탐색
while queue:
x, y = queue.popleft()
# 네 방향 탐색 (상, 하, 좌, 우)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 유효한 범위인지 확인하고, 이동 가능한 1인 경우에만 이동
if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 1:
# 새로운 위치에 이전 거리 + 1을 저장
matrix[nx][ny] = matrix[x][y] + 1
# 큐에 새로운 위치 추가
queue.append((nx, ny))
# 도착지점(N-1, M-1)의 값이 최단 거리
return matrix[N-1][M-1]
# 입력 받기
N, M = map(int, input().split())
matrix = [list(map(int, input().strip())) for _ in range(N)]
# BFS 수행 및 결과 출력
print(bfs(matrix, N, M))나는 아직 이걸 직접 작성하기 어려워서 GPT한테 부탁해 봤다 (고맙다!!)
N, M에 행과 열의 크기를 입력받고
matrix에 각 행을 입력받아서 2차원 리스트로 저장한다.
여기까지는 내가 생각한 것과 동일!
이제 다른 점은 BFS 함수를 사용하는 부분이다
큐(queue) : BFS는 큐를 사용해서 현재 위치에서 다음으로 이동할 수 있는 위치를 탐색한다고 한다
그래서 큐가 뭔데? (이왕 적는 거 제대로 이해하고 가고 싶은 마음이라 적어봄)
큐는 데이터를 저장하고 처리하는 자료구조 중 하나로, 선입선출(가게에서 음료 냉장고에 넣을 때 하는 것처럼) 원칙을 따른다. 즉, 먼저 들어간 데이터가 먼저 나오는 구조!
줄을 서는 상황과 비슷하다고 생각하면 된다. 먼저 줄 선 사람이 먼저 나가는 것처럼
그리고 입구와 출구가 따로 있음!
한쪽 끝에서 데이터를 넣고(Enqueue)
다른 쪽 끝에서 데이터를 꺼내는(Dequeue) 구조를 가짐
큐의 주요 연산?
Enqueue(삽입): 큐의 뒤쪽에 데이터를 추가
Dequeue(삭제): 큐의 앞쪽에서 데이터를 꺼내고 제거
Peek(탐색): 큐의 앞쪽에 있는 데이터를 확인하지만, 제거하지는 않음
isEmpty(비어있는지 확인): 큐가 비어 있는지 여부를 확인
[1, 2, 3, 4, 5] <- 큐 상태
1. Enqueue: 6을 추가하면 -> [1, 2, 3, 4, 5, 6]
2. Dequeue: 1을 꺼내면 -> [2, 3, 4, 5, 6] (1은 제거됨)
from collections import deque
# 큐 초기화
queue = deque()
# Enqueue: 데이터 삽입
queue.append(1)
queue.append(2)
queue.append(3)
print(queue) # deque([1, 2, 3])
# Dequeue: 데이터 꺼내기
first = queue.popleft()
print(first) # 1 (맨 앞에 있는 데이터가 꺼내짐)
print(queue) # deque([2, 3])이렇게 코드를 작성하면 큐의 연산을 매우 빠르게 수행할 수 있다고 한다
큐의 사용 사례?
순서를 유지하면서 데이터를 처리해야 하는 경우에 많이 사용한다고 함 (선입 선출 구조이기 때문인듯함)
1. 프로세스 스케일링 (운영체제에서 프로세스가 순서대로 처리되도록 하는 데 사용)
2. 프린터 작업 관리 (프린터에 여러 개의 작업을 순차적으로 처리할 때 사용)
3. BFS 너비 우선 탐색 (그래프 탐색 알고리즘 BFS에서 큐를 사용해서 방문할 노드를 순차적으로 처리)
from collections import deque
def bfs(graph, start):
queue = deque([start]) # 큐에 시작 노드를 삽입
visited = set([start]) # 방문한 노드를 기록
while queue:
node = queue.popleft() # 큐에서 가장 앞에 있는 노드를 꺼내서 탐색
print(node, end=' ') # 현재 노드를 방문 처리
# 이웃 노드 탐색
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor) # 이웃 노드를 큐에 추가
# 그래프 예시
graph = {
1: [2, 3, 4],
2: [1, 5],
3: [1, 6],
4: [1],
5: [2],
6: [3]
}
# BFS 탐색 실행
bfs(graph, 1) # 출력: 1 2 3 4 5 6
수학에서 기본적으로 배웠던 방향벡터(dx, dy)도 나오는데
상하좌우로 이동하기 위한 방향을 미리 정의해 두고,
dx, dy 리스트는 각각 상하좌우로 이동하는 x, y 좌표의 변화량을 나타낸다고 한다
dx = [-1, 1, 0, 0]은 각각 위, 아래, 왼쪽, 오른쪽으로 이동할 때 x 좌표의 변화를
dy = [0, 0, -1, 1]은 각각 위, 아래, 왼쪽, 오른쪽으로 이동할 때 y 좌표의 변화를 나타낸다
거리 갱신 부분은 matrix [x][y]에서 이동할 수 있는 위치로 이동할 때, 그 위치의 값은 현재 위치의 값에 1을 더해 갱신하여
최단 경로를 구한다!
쉽게 이야기하면!
시작점 (0, 0)에서 BFS를 시작
상하좌우로 이동할 수 있는지 체크하고
이동 가능한 위치(값이 1인 곳)로 이동하며 거리를 갱신
BFS가 끝나면 matrix [N-1][M-1]에 저장된 값이 출발점에서 도착점까지의 최단 거리가 된다!!!!!
그리고 혼자 생각해 본 게 '만약 0이 있는 곳만 이동 가능하면 코드를 어떻게 수정해야 할까?'인데
matrix [nx][ny] == 1에서 matrix [nx][ny] == 0으로 바꿔야 하고
출발점도 0이어야만 하므로, 출발점도 matrix [0][0]이 0인지 확인해야 함!
from collections import deque
# BFS 함수 정의
def bfs(matrix, N, M):
dx = [-1, 1, 0, 0] # 상, 하, 좌, 우 방향 벡터
dy = [0, 0, -1, 1]
queue = deque([(0, 0)]) # 시작점 추가
matrix[0][0] = 1 # 출발점(0, 0)의 거리를 1로 설정
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 유효 범위 내에서 0인 곳만 이동 가능
if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 0:
matrix[nx][ny] = matrix[x][y] + 1 # 이전 거리 + 1로 갱신
queue.append((nx, ny))
return matrix[N-1][M-1]
# 입력 받기
N, M = map(int, input().split())
matrix = [list(map(int, input().strip())) for _ in range(N)]
# BFS 수행 및 결과 출력
result = bfs(matrix, N, M)
if result == 0:
print(-1) # 도착할 수 없는 경우
else:
print(result)
더 붙이면 코드의 시간 복잡도 부분
BFS는 모든 노드를 한 번씩 방문하므로 O(N * M)의 시간 복잡도를 가진다
공간 복잡도는 큐와 행렬을 사용하여 O(N * M)의 공간을 사용한다고 한다.
시간복잡도와 공간 복잡도까지 이 글에서 다루면 너무 길어질 것 같아서 다음에 포스팅하는 걸로
코딩하는 게 맘처럼 쉽지 않다~ ㅠ
