문제 핵심
이 문제는 출발점 (0, 0)에서 도착점 (n - 1, n - 1)까지 이동하면서 최소 비용으로 경주로를 건설하는 문제다.
이동은 상하좌우 4방향으로 가능하고, 벽이 있는 칸은 지나갈 수 없다.
도로 건설 비용은 다음과 같다.
- 직선 도로:
100원 - 코너:
500원
방향을 유지해서 이동하면 직선 도로만 추가되므로 100원이 든다.
방향을 바꿔 이동하면 직선 도로 100원과 코너 500원이 함께 필요하므로 총 600원이 든다.
왜 방향을 함께 저장해야 할까?
같은 칸에 도착하더라도 어떤 방향으로 들어왔는지에 따라 이후 비용이 달라진다.
예를 들어 어떤 칸 (x, y)에 도착했다고 하자.
이때 오른쪽 방향으로 들어온 경우와 아래쪽 방향으로 들어온 경우는 다음 이동에서 코너 발생 여부가 다를 수 있다.
따라서 단순히 다음과 같이 저장하면 부족하다.
cost[x][y]대신 방향까지 포함해서 저장해야 한다.
cost[x][y][direction]의미는 다음과 같다.
(x, y)에 direction 방향으로 도착했을 때의 최소 비용방향 정의
코드에서는 방향을 다음과 같이 정의한다.
# 상, 우, 하, 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]각 인덱스는 다음 방향을 의미한다.
| direction | 방향 | 이동 |
|---|---|---|
| 0 | 상 | (-1, 0) |
| 1 | 우 | (0, 1) |
| 2 | 하 | (1, 0) |
| 3 | 좌 | (0, -1) |
비용 배열
cost = [[[float('inf')] * 4 for _ in range(n)] for _ in range(n)]cost[x][y][dir]은 (x, y)에 dir 방향으로 도착했을 때의 최소 비용이다.
처음에는 아직 어떤 칸도 방문하지 않았으므로 무한대로 초기화한다.
시작점 처리
시작점 (0, 0)에서는 이전 방향이 없다.
따라서 4방향 모두 비용 0으로 시작한다.
for d in range(4):
cost[0][0][d] = 0
q.append((0, 0, d, 0))이렇게 하면 첫 이동에서 특정 방향을 불리하게 만들지 않을 수 있다.
예를 들어 처음 오른쪽으로 가든 아래쪽으로 가든 직선 도로 비용 100만 들게 된다.
이동 비용 계산
현재 방향과 다음 이동 방향이 같으면 직선 도로다.
if direction == nd:
next_cost = current_cost + 100방향이 바뀌면 코너가 생긴다.
else:
next_cost = current_cost + 600여기서 600은 다음 비용의 합이다.
직선 도로 100 + 코너 500 = 600더 싼 경로만 큐에 넣기
어떤 칸에 특정 방향으로 도착하는 더 싼 비용을 찾았다면 값을 갱신하고 다시 탐색한다.
if cost[nx][ny][nd] > next_cost:
cost[nx][ny][nd] = next_cost
q.append((nx, ny, nd, next_cost))이 부분이 중요하다.
같은 칸이라도 방향이 다르면 다른 상태로 취급해야 한다.
또한 이미 방문했던 상태라도 더 낮은 비용으로 도착할 수 있다면 다시 탐색해야 한다.
전체 코드
from collections import deque
def solution(board):
n = len(board)
# 상, 우, 하, 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# cost[x][y][dir] = (x, y)에 dir 방향으로 도착했을 때 최소 비용
cost = [[[float("inf")] * 4 for _ in range(n)] for _ in range(n)]
q = deque()
# 시작점에서는 방향이 없으므로 4방향 모두 0으로 시작
for d in range(4):
cost[0][0][d] = 0
q.append((0, 0, d, 0))
while q:
x, y, direction, current_cost = q.popleft()
for nd in range(4):
nx = x + dx[nd]
ny = y + dy[nd]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] == 1:
continue
# 같은 방향이면 직선 도로
if direction == nd:
next_cost = current_cost + 100
# 방향이 바뀌면 코너 + 직선 도로
else:
next_cost = current_cost + 600
if cost[nx][ny][nd] > next_cost:
cost[nx][ny][nd] = next_cost
q.append((nx, ny, nd, next_cost))
return min(cost[n - 1][n - 1])예시로 이해하기
다음과 같은 보드가 있다고 하자.
board = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
]가장 단순한 경로는 오른쪽으로 2번, 아래로 2번 이동하는 것이다.
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)비용은 다음과 같다.
오른쪽 이동: 100
오른쪽 이동: 100
아래 이동: 600
아래 이동: 100총 비용:
900방향이 바뀌는 지점에서 코너 비용이 추가된다.
왜 단순 방문 배열로는 안 될까?
일반적인 BFS에서는 한 번 방문한 칸을 다시 방문하지 않는다.
하지만 이 문제에서는 같은 칸에 도착해도 방향에 따라 이후 비용이 달라진다.
예를 들어 (2, 2)에 도착했더라도,
- 오른쪽 방향으로 도착한 경우
- 아래쪽 방향으로 도착한 경우
다음 이동에서 코너가 생기는지 여부가 다르다.
따라서 다음과 같은 단순 방문 처리는 사용할 수 없다.
visited[x][y] = True반드시 방향별 최소 비용을 저장해야 한다.
정답 계산
도착점 (n - 1, n - 1)에 도착하는 방향은 여러 가지일 수 있다.
우리는 그중 최소 비용만 필요하다.
return min(cost[n - 1][n - 1])시간 복잡도
보드 크기를 n x n이라고 하자.
각 칸마다 방향 상태가 4개 있다.
상태 수 = n x n x 4각 상태에서 4방향을 확인한다.
따라서 시간 복잡도는 대략 다음과 같다.
O(n^2)정확히는 방향 4개가 붙지만 상수이므로 O(n^2)로 볼 수 있다.
공간 복잡도
방향별 비용 배열을 저장한다.
O(n^2 x 4)상수 4를 제외하면 다음과 같다.
O(n^2)정리
이 문제의 핵심은 같은 칸이라도 어떤 방향으로 들어왔는지에 따라 다른 상태로 봐야 한다는 점이다.
풀이 흐름은 다음과 같다.
- 각 칸마다 4방향 비용을 저장한다.
- 시작점은 방향이 없으므로 4방향 모두 비용 0으로 시작한다.
- 현재 방향과 다음 방향이 같으면
100을 더한다. - 방향이 바뀌면
600을 더한다. - 더 낮은 비용으로 도착할 수 있을 때만 큐에 넣는다.
- 도착점의 4방향 비용 중 최솟값을 반환한다.
단순 최단 거리 문제가 아니라, 방향에 따라 비용이 달라지는 최단 비용 문제라는 점을 기억하면 된다.
