문제 요약
n x m 크기의 퍼즐판에 빨간 수레와 파란 수레가 있다.
각 수레는 자신의 시작 칸에서 출발해 자신의 도착 칸까지 이동해야 한다.
매 턴마다 두 수레는 동시에 움직인다.
단, 이미 도착 칸에 도착한 수레는 더 이상 움직이지 않고 그 자리에 고정된다.
이동할 때는 다음 규칙을 지켜야 한다.
- 격자 밖으로 나갈 수 없다.
- 벽으로 이동할 수 없다.
- 각 수레는 자신이 이미 방문했던 칸으로 이동할 수 없다.
- 두 수레가 동시에 같은 칸으로 이동할 수 없다.
- 두 수레가 서로 자리를 바꾸며 이동할 수 없다.
두 수레를 모두 도착 칸으로 이동시키는 데 필요한 최소 턴 수를 구해야 한다.
불가능하면 0을 반환한다.
칸 번호 의미
문제에서 주어지는 maze의 값은 다음과 같이 해석한다.
0: 빈 칸
1: 빨간 수레 시작 칸
2: 파란 수레 시작 칸
3: 빨간 수레 도착 칸
4: 파란 수레 도착 칸
5: 벽핵심 아이디어
이 문제는 두 수레가 동시에 움직이므로 상태를 다음처럼 관리해야 한다.
빨간 수레 위치
파란 수레 위치
빨간 수레 방문 기록
파란 수레 방문 기록
현재 턴 수각 수레는 자신이 방문했던 칸으로 다시 이동할 수 없으므로, 방문 기록을 수레별로 따로 관리해야 한다.
격자 크기가 작기 때문에 각 칸을 하나의 비트로 표현하면 방문 여부를 효율적으로 저장할 수 있다.
방문 기록 비트마스크
칸 (x, y)를 하나의 번호로 바꾼다.
idx = x * m + y해당 칸을 방문했다면 방문 비트마스크에 다음 값을 추가한다.
visited | (1 << idx)방문 여부는 다음과 같이 확인한다.
visited & (1 << idx)풀이 과정
1. 시작 위치와 도착 위치 찾기
maze를 순회하면서 다음 위치를 찾는다.
- 빨간 수레 시작 위치
- 파란 수레 시작 위치
- 빨간 수레 도착 위치
- 파란 수레 도착 위치
2. DFS로 모든 가능한 이동 탐색
각 턴마다 빨간 수레와 파란 수레의 다음 위치 후보를 만든다.
수레가 이미 도착 칸에 있다면 이동하지 않고 현재 위치만 후보가 된다.
아직 도착하지 않았다면 상하좌우 네 방향으로 이동 가능한 칸을 후보로 만든다.
3. 두 수레의 동시 이동 검증
빨간 수레의 다음 위치와 파란 수레의 다음 위치를 조합할 때 다음 경우는 제외한다.
두 수레가 같은 칸으로 이동하는 경우
두 수레가 서로 자리를 바꾸는 경우조건을 만족하는 이동만 다음 DFS 상태로 넘긴다.
4. 최소 턴 갱신
두 수레가 모두 도착 칸에 도착하면 정답을 갱신한다.
이미 찾은 정답보다 현재 턴 수가 크거나 같다면 더 탐색할 필요가 없으므로 가지치기한다.
Python 코드
def solution(maze):
n = len(maze)
m = len(maze[0])
red_start = blue_start = None
red_goal = blue_goal = None
for i in range(n):
for j in range(m):
if maze[i][j] == 1:
red_start = (i, j)
elif maze[i][j] == 2:
blue_start = (i, j)
elif maze[i][j] == 3:
red_goal = (i, j)
elif maze[i][j] == 4:
blue_goal = (i, j)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
answer = float("inf")
def cell_bit(x, y):
return 1 << (x * m + y)
def get_next_positions(x, y, visited, goal):
if (x, y) == goal:
return [(x, y)]
positions = []
for dx, dy in directions:
nx = x + dx
ny = y + dy
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if maze[nx][ny] == 5:
continue
bit = cell_bit(nx, ny)
if visited & bit:
continue
positions.append((nx, ny))
return positions
def dfs(red, blue, red_visited, blue_visited, turn):
nonlocal answer
if turn >= answer:
return
if red == red_goal and blue == blue_goal:
answer = turn
return
red_next_positions = get_next_positions(
red[0],
red[1],
red_visited,
red_goal,
)
blue_next_positions = get_next_positions(
blue[0],
blue[1],
blue_visited,
blue_goal,
)
for next_red in red_next_positions:
for next_blue in blue_next_positions:
if next_red == next_blue:
continue
if next_red == blue and next_blue == red:
continue
next_red_visited = red_visited | cell_bit(next_red[0], next_red[1])
next_blue_visited = blue_visited | cell_bit(next_blue[0], next_blue[1])
dfs(
next_red,
next_blue,
next_red_visited,
next_blue_visited,
turn + 1,
)
initial_red_visited = cell_bit(red_start[0], red_start[1])
initial_blue_visited = cell_bit(blue_start[0], blue_start[1])
dfs(
red_start,
blue_start,
initial_red_visited,
initial_blue_visited,
0,
)
if answer == float("inf"):
return 0
return answer코드 설명
위치 찾기
if maze[i][j] == 1:
red_start = (i, j)
elif maze[i][j] == 2:
blue_start = (i, j)
elif maze[i][j] == 3:
red_goal = (i, j)
elif maze[i][j] == 4:
blue_goal = (i, j)퍼즐판을 순회하면서 시작 칸과 도착 칸을 저장한다.
방문 비트 계산
def cell_bit(x, y):
return 1 << (x * m + y)각 칸을 하나의 비트로 표현한다.
이를 이용해 각 수레가 어떤 칸을 방문했는지 빠르게 확인할 수 있다.
다음 위치 후보 생성
def get_next_positions(x, y, visited, goal):현재 수레가 이동할 수 있는 다음 위치들을 반환한다.
이미 도착 칸에 있다면 움직이지 않아야 하므로 현재 위치만 반환한다.
if (x, y) == goal:
return [(x, y)]도착하지 않은 경우에는 상하좌우 이동을 확인한다.
방문한 칸 제외
if visited & bit:
continue각 수레는 자신이 방문했던 칸으로 다시 이동할 수 없다.
빨간 수레와 파란 수레의 방문 기록은 서로 독립적으로 관리한다.
같은 칸 이동 방지
if next_red == next_blue:
continue두 수레는 동시에 같은 칸으로 이동할 수 없다.
자리 바꾸기 방지
if next_red == blue and next_blue == red:
continue빨간 수레와 파란 수레가 서로의 현재 위치로 동시에 이동하는 경우도 불가능하다.
가지치기
if turn >= answer:
return이미 더 짧은 턴 수로 답을 찾았다면, 그보다 길거나 같은 경로는 탐색하지 않는다.
시간 복잡도
각 턴마다 빨간 수레와 파란 수레가 각각 최대 4개의 이동 후보를 가진다.
격자 크기가 작고, 각 수레는 같은 칸을 다시 방문할 수 없기 때문에 탐색 깊이는 제한된다.
상태 수를 기준으로 보면 다음과 같이 볼 수 있다.
O(상태 수)각 상태는 다음 정보로 구성된다.
빨간 위치 x 파란 위치 x 빨간 방문 상태 x 파란 방문 상태공간 복잡도
DFS 재귀 호출 깊이는 각 수레가 방문할 수 있는 칸 수에 의해 제한된다.
격자 칸 수를 N = n * m이라고 하면 공간 복잡도는 다음과 같다.
O(N)방문 비트마스크는 정수 하나로 관리한다.
정리
이 문제는 두 수레가 동시에 움직이기 때문에 단순 최단 거리 문제가 아니다.
핵심은 다음과 같다.
- 빨간 수레와 파란 수레의 방문 기록을 따로 관리한다.
- 도착한 수레는 더 이상 움직이지 않는다.
- 같은 칸 이동과 자리 바꾸기를 반드시 막는다.
- DFS로 가능한 동시 이동을 탐색하면서 최소 턴을 갱신한다.
격자가 작고 재방문이 금지되어 있으므로, 비트마스크 방문 기록과 백트래킹으로 해결할 수 있다.
