문제 설명
N × M 크기의 게임 맵이 주어집니다.
1: 이동 가능한 칸0: 벽
캐릭터는 (0, 0)에서 출발하여 (N-1, M-1) 위치까지 이동해야 합니다.
상하좌우로만 이동할 수 있으며, 지나가야 하는 칸의 최소 개수를 구하는 문제입니다.
도착할 수 없는 경우에는 -1을 반환해야 합니다.
풀이 아이디어
이 문제는 최단 거리를 구해야 하므로 BFS(Breadth First Search)를 사용하는 것이 가장 적합합니다.
BFS는 가까운 노드부터 차례대로 탐색하기 때문에 특정 위치에 처음 도착했을 때의 거리가 곧 최단 거리입니다.
탐색 과정
- 시작 위치
(0, 0)을 큐에 넣는다. - 현재 위치에서 상하좌우를 확인한다.
- 이동 가능한 칸(
1)이라면- 현재 위치의 값 + 1을 저장한다.
- 큐에 추가한다.
- BFS 탐색이 끝난 후
- 도착 지점 값이 그대로
1이면 도달하지 못한 경우이므로-1반환 - 그렇지 않으면 저장된 거리를 반환
- 도착 지점 값이 그대로
코드
from collections import deque
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def bfs(maps):
n = len(maps)
m = len(maps[0])
q = deque()
q.append((0, 0))
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if maps[nx][ny] == 0:
continue
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
q.append((nx, ny))
if maps[n - 1][m - 1] == 1:
return -1
return maps[n - 1][m - 1]
def solution(maps):
return bfs(maps)코드 설명
방향 벡터
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]상, 우, 하, 좌 방향으로 이동하기 위한 배열입니다.
예를 들어 현재 위치가 (x, y)라면
nx = x + dx[i]
ny = y + dy[i]를 통해 인접한 칸으로 이동할 수 있습니다.
큐 생성 및 시작 위치 삽입
q = deque()
q.append((0, 0))BFS 탐색을 위해 큐를 사용합니다.
시작 위치인 (0, 0)을 먼저 넣어줍니다.
BFS 탐색
while q:
x, y = q.popleft()큐에서 현재 위치를 꺼내면서 탐색을 진행합니다.
범위 검사
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue맵 밖으로 이동하는 경우는 무시합니다.
벽 검사
if maps[nx][ny] == 0:
continue벽은 이동할 수 없으므로 건너뜁니다.
거리 저장
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
q.append((nx, ny))처음 방문한 칸이라면
현재 위치까지의 거리 + 1 값을 저장합니다.
예를 들어
1 1 1
0 1 0
0 1 1에서 (0,0) → (0,1) 이동 시
1 2 1
0 1 0
0 1 1이 되고,
계속 탐색하면
1 2 3
0 3 0
0 4 5처럼 최단 거리가 저장됩니다.
도착 가능 여부 확인
if maps[n - 1][m - 1] == 1:
return -1도착 지점 값이 여전히 1이라면 방문하지 못한 것이므로 -1을 반환합니다.
최종 거리 반환
return maps[n - 1][m - 1]도착 지점에 저장된 값이 최단 거리입니다.
시간 복잡도
맵의 크기를 N × M이라고 할 때
각 칸은 최대 한 번씩만 방문합니다.
따라서
시간 복잡도 : O(N × M)
공간 복잡도 : O(N × M)정리
이 문제는 대표적인 BFS 최단거리 문제입니다.
핵심은 방문 여부를 별도의 배열로 관리하지 않고, maps 배열 자체에 거리를 저장하여 공간을 절약하는 것입니다.
또한 BFS의 특성상 먼저 도착한 경로가 최단 거리이므로 별도의 최단 거리 비교 과정 없이 해결할 수 있습니다.
