2차원 행렬에서 각 칸(cell)의 위치는 왼쪽, 오른쪽, 위, 아래 네 방향으로 분석할 수 있습니다.
너비 우선 탐색(Breadth First Search, BFS)은 주어진 2차원 행렬에서 두 요소 사이의 최단 거리를 찾는 알고리즘입니다. 즉, 각 칸에서 수행할 수 있는 이동은 네 가지이며, 이를 다음과 같은 숫자 값으로 표현할 수 있습니다.
- '2': 해당 칸이 출발지(Source)임을 나타냅니다.
- '3': 해당 칸이 목적지(Destination)임을 나타냅니다.
- '1': 해당 칸으로 이동할 수 있으며, 그 방향으로 계속 진행 가능함을 나타냅니다.
- '0': 해당 칸은 어떤 방향으로도 이동할 수 없음을 나타냅니다.
이러한 규칙을 바탕으로 주어진 행렬에 대해 너비 우선 탐색을 수행할 수 있습니다.
문제 해결 접근 방식
BFS를 사용해 행렬 전체를 탐색하고 임의의 두 칸 사이의 최소(최단) 거리를 찾는 알고리즘은 다음과 같습니다.
- 먼저 행(row)과 열(column)의 크기를 입력받습니다.
- 주어진 행과 열의 크기로 행렬을 초기화합니다.
- 정수 함수
shortestDist(int row, int col, int mat[][col])는 행, 열, 행렬을 입력으로 받아 행렬 내 요소들 간의 최단 거리를 반환합니다. - 출발지(source)와 목적지(destination) 변수를 초기화하여 해당 요소들의 위치를 찾습니다.
- 요소가 '3'이면 목적지로 표시하고, '2'이면 출발지로 표시합니다.
- 큐(queue) 자료구조를 초기화하여 주어진 행렬에 BFS를 적용합니다.
- 행렬의 행과 열 좌표를 쌍(pair) 형태로 큐에 삽입합니다. 이후 각 칸으로 이동하며 그 칸이 목적지인지 확인합니다. 만약 목적지까지의 거리가 현재 경로보다 짧다면 거리 값을 갱신합니다.
- 다른 방향으로도 이동하며 현재 칸으로부터의 최소 거리를 계속 탐색합니다.
- 최종적으로 최소 거리를 결과로 반환합니다.
예제 코드
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2 :
source_i = i
source_j = j
if mat[i][j] == 3 :
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# 큐를 초기화하여 행렬에 대한 BFS 시작
q = queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# 조건 검사를 추가한 수정된 BFS
while (not q.empty()):
# 큐의 맨 앞에서 노드를 꺼내고 제거
temp = q.get()
x = temp.row_num
y = temp.col_num
# 왼쪽으로 이동이 허용되거나 목적지 칸인 경우
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
# 왼쪽 칸까지의 거리가 기존 계산된 경로 거리보다 짧으면 갱신
if dist[x][y] + 1 < dist[x][y - 1] :
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# 오른쪽으로 이동이 허용되거나 목적지 칸인 경우
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
# 오른쪽 칸까지의 거리가 기존 계산된 경로 거리보다 짧으면 갱신
if dist[x][y] + 1 < dist[x][y + 1] :
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next);
# 위로 이동이 허용되거나 목적지 칸인 경우
if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3) :
# 위쪽 칸까지의 거리가 기존 계산된 경로 거리보다 짧으면 갱신
if dist[x][y] + 1 < dist[x - 1][y] :
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# 아래로 이동이 허용되거나 목적지 칸인 경우
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
# 아래쪽 칸까지의 거리가 기존 계산된 경로 거리보다 짧으면 갱신
if dist[x][y] + 1 < dist[x + 1][y] :
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1] ]
answer = findDistance(row, col, mat);
if answer == INF :
print("No Path Found")
else:
print("출발지와 목적지 사이의 최단 거리:")
print(answer)실행 결과
출발지와 목적지 사이의 최단 거리: 2
동작 원리 정리
위 코드의 핵심 흐름을 요약하면 다음과 같습니다.
- 출발지·목적지 탐색: 행렬을 한 번 순회하면서 값이 '2'인 칸은 출발지로, '3'인 칸은 목적지로 기록합니다.
- 거리 배열 초기화: 모든 칸의 거리를 무한대(INF)로 설정한 뒤, 출발지만 0으로 초기화합니다.
- BFS 수행: 큐에서 칸을 하나씩 꺼내 네 방향(상·하·좌·우)을 검사합니다. 이동 가능한 칸('1' 또는 '3')이고, 기존에 계산된 거리보다 더 짧은 경로를 발견하면 거리를 갱신하고 해당 칸을 큐에 삽입합니다.
- 결과 반환: 탐색이 끝나면 목적지 칸의 거리 값을 반환합니다. 값이 여전히 INF라면 경로가 존재하지 않는 것입니다.
이 알고리즘의 시간 복잡도는 행렬의 모든 칸을 최대 한 번씩 방문하므로 O(row × col)이며, 공간 복잡도 역시 거리 배열과 큐를 위해 O(row × col)입니다. BFS는 가중치가 없는 격자(grid) 환경에서 최단 경로를 보장하기 때문에 미로 찾기, 게임 맵 탐색 등 다양한 문제에 활용됩니다.