N × N 크기의 행렬 M이 주어집니다. 이 행렬은 0, 1, 2, 3 네 가지 값으로 채워져 있으며, 출발점(Source)에서 도착점(Destination)까지 빈 칸(Blank cell)을 통해서만 상·하·좌·우로 이동할 때 필요한 최소 이동 횟수를 구해야 합니다.
셀 값의 의미
- 1: 출발점 (Source) — 단 하나만 존재
- 2: 도착점 (Destination) — 단 하나만 존재
- 3: 빈 칸 (Blank cell) — 이동 가능
- 0: 벽 (Wall) — 이동 불가
이동 한 번당 비용은 1로 계산합니다. 예를 들어 아래 4×4 행렬에서
| 3 | 3 | 1 | 0 |
|---|---|---|---|
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
출발점(값 1)에서 도착점(값 2)까지 최단 경로는 5번 이동이며, 아래 표에서 초록색으로 표시된 경로입니다.
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
해결 접근법: 그래프 + BFS
행렬의 각 이동 가능 셀(값이 0이 아닌 셀)을 그래프의 정점으로 간주하고, 인접한 이동 가능 셀 간에 간선을 연결합니다. 그런 다음 출발점 정점에서 도착점 정점까지 너비 우선 탐색(BFS)을 수행해 최단 거리(레벨)를 구합니다.
알고리즘 단계
nodes = order × order + 2개의 정점을 가진 그래프g생성- 행렬을 순회하며 각 셀
(i, j)에 대해:- 셀 값이 0이 아니면(이동 가능하면) 고유 번호
k할당 - 상·하·좌·우 인접 셀이 유효 범위 내에 있고 값이 0이 아니면
k와 해당 인접 셀 번호 사이에 무방향 간선 추가 - 셀 값이 1이면
src = k, 2이면dest = k저장 k증가
- 셀 값이 0이 아니면(이동 가능하면) 고유 번호
g.BFS(src, dest)수행해 최소 이동 횟수 반환
파이썬 구현 예제
아래 코드는 위 알고리즘을 구현한 것입니다. 주의: 원본 코드의 BFS 구현에 버그(pop()로 스택처럼 동작, 레벨 업데이트 조건 오류 등)가 있어 올바른 결과(5)가 나오지 않습니다. 아래는 수정된 올바른 버전입니다.
from collections import deque
class Graph:
def __init__(self, nodes: int):
self.nodes = nodes
self.adj = [[] for _ in range(nodes)]
def insert_edge(self, src: int, dest: int):
self.adj[src].append(dest)
self.adj[dest].append(src)
def bfs(self, src: int, dest: int) -> int:
if src == dest:
return 0
level = [-1] * self.nodes
q = deque([src])
level[src] = 0
while q:
u = q.popleft()
for v in self.adj[u]:
if level[v] == -1:
level[v] = level[u] + 1
if v == dest:
return level[v]
q.append(v)
return -1 # 도달 불가
def is_ok(i: int, j: int, mat: list[list[int]], order: int) -> bool:
return 0 <= i < order and 0 <= j < order and mat[i][j] != 0
def get_min_moves(mat: list[list[int]]) -> int:
order = len(mat)
src = dest = -1
nodes = order * order + 2
g = Graph(nodes)
k = 1
for i in range(order):
for j in range(order):
if mat[i][j] != 0:
# 오른쪽
if is_ok(i, j + 1, mat, order):
g.insert_edge(k, k + 1)
# 왼쪽
if is_ok(i, j - 1, mat, order):
g.insert_edge(k, k - 1)
# 아래
if is_ok(i + 1, j, mat, order):
g.insert_edge(k, k + order)
# 위
if is_ok(i - 1, j, mat, order):
g.insert_edge(k, k - order)
if mat[i][j] == 1:
src = k
elif mat[i][j] == 2:
dest = k
k += 1
return g.bfs(src, dest)
# 테스트
if __name__ == "__main__":
mat = [
[3, 3, 1, 0],
[3, 0, 3, 3],
[3, 3, 0, 3],
[0, 3, 2, 3]
]
print(get_min_moves(mat)) # 출력: 5
입력 예시
[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]출력
5핵심 포인트
- 행렬을 그래프로 변환해 BFS로 최단 경로 탐색 — 전형적인 그리드 최단 경로 문제
- BFS는
deque를 사용해 큐(FIFO)로 구현해야 레벨 단위 탐색 보장 - 방문 배열(
level)로 중복 방문 방지 및 거리 기록 - 시간 복잡도: O(N²) — 각 셀과 간선을 상수 시간에 처리