문제 요약
4 x 4 보드에서 같은 그림 카드 두 장을 선택해 제거한다. 방향키 이동, Ctrl + 방향키 이동, Enter 입력은 각각 1회 조작으로 센다.
현재 커서 위치에서 모든 카드 쌍을 제거하는 최소 조작 횟수를 구한다.
핵심 아이디어
이 문제에는 두 종류의 탐색이 필요하다.
- BFS: 현재 남은 카드 상태에서 한 커서 위치에서 다른 위치까지의 최소 이동 횟수를 구한다.
- DFS + 메모이제이션: 어떤 카드 쌍부터 제거할지, 그 카드 쌍에서 어느 카드를 먼저 선택할지 탐색한다.
카드 종류는 최대 6개이므로 제거 순서는 최대 6!개다. 각 쌍은 두 카드 중 어느 쪽을 먼저 선택할지 2가지 경우가 있으므로, 모든 경우를 탐색해도 충분하다.
남은 카드 상태를 비트마스크로 표현하기
카드 숫자는 1부터 6까지다. 어떤 카드 종류가 제거되었는지를 비트로 표현한다.
mask의 k번 비트가 1: 숫자 k 카드 쌍은 이미 제거됨
mask의 k번 비트가 0: 숫자 k 카드 쌍이 아직 남아 있음보드를 직접 수정하지 않아도 mask만으로 현재 칸에 카드가 남아 있는지 판단할 수 있다.
def has_card(row, col, removed_mask):
value = board[row][col]
return value != 0 and (removed_mask & (1 << value)) == 0Ctrl 이동 처리
Ctrl + 방향키는 해당 방향으로 이동하다가 다음 중 하나를 만나면 멈춘다.
- 가장 가까운 남은 카드
- 보드의 끝
따라서 한 칸씩 전진하면서 카드 또는 경계를 만날 때까지 확인한다.
DFS 상태
dfs(removed_mask, row, col)은 현재 커서 위치와 제거된 카드 상태에서, 남은 카드를 모두 제거하는 최소 조작 횟수다.
아직 남은 카드 종류 하나를 골라 두 장을 제거한다.
- 첫 번째 카드 → 두 번째 카드 순서
- 두 번째 카드 → 첫 번째 카드 순서
두 경우를 모두 계산한다. 카드 한 쌍을 선택하려면 Enter가 두 번 필요하므로 이동 횟수에 2를 더한다.
Python 코드
from collections import deque
from functools import lru_cache
def solution(board, r, c):
positions = {}
for row in range(4):
for col in range(4):
value = board[row][col]
if value != 0:
positions.setdefault(value, []).append((row, col))
card_numbers = list(positions)
full_mask = sum(1 << number for number in card_numbers)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def has_card(row, col, removed_mask):
value = board[row][col]
return value != 0 and (removed_mask & (1 << value)) == 0
def ctrl_move(row, col, dr, dc, removed_mask):
while True:
next_row = row + dr
next_col = col + dc
# 해당 방향의 끝 칸에서 멈춘다.
if not (0 <= next_row < 4 and 0 <= next_col < 4):
return row, col
row, col = next_row, next_col
if has_card(row, col, removed_mask):
return row, col
def move_distance(start_row, start_col, target_row, target_col, removed_mask):
visited = [[False] * 4 for _ in range(4)]
visited[start_row][start_col] = True
queue = deque([(start_row, start_col, 0)])
while queue:
row, col, distance = queue.popleft()
if (row, col) == (target_row, target_col):
return distance
for dr, dc in directions:
# 일반 방향키 이동
next_row = row + dr
next_col = col + dc
if (
0 <= next_row < 4
and 0 <= next_col < 4
and not visited[next_row][next_col]
):
visited[next_row][next_col] = True
queue.append((next_row, next_col, distance + 1))
# Ctrl + 방향키 이동
next_row, next_col = ctrl_move(
row,
col,
dr,
dc,
removed_mask
)
if not visited[next_row][next_col]:
visited[next_row][next_col] = True
queue.append((next_row, next_col, distance + 1))
@lru_cache(None)
def dfs(removed_mask, row, col):
if removed_mask == full_mask:
return 0
minimum = float("inf")
for number in card_numbers:
bit = 1 << number
if removed_mask & bit:
continue
first, second = positions[number]
next_mask = removed_mask | bit
# first 카드를 먼저 선택하는 경우
first_to_second = (
move_distance(row, col, *first, removed_mask)
+ move_distance(*first, *second, removed_mask)
+ 2
+ dfs(next_mask, *second)
)
# second 카드를 먼저 선택하는 경우
second_to_first = (
move_distance(row, col, *second, removed_mask)
+ move_distance(*second, *first, removed_mask)
+ 2
+ dfs(next_mask, *first)
)
minimum = min(minimum, first_to_second, second_to_first)
return minimum
return dfs(0, r, c)코드 설명
카드 쌍을 제거하기 전까지 두 카드는 보드에 남아 있어야 한다. 따라서 첫 카드에서 두 번째 카드로 이동할 때도 removed_mask는 아직 바꾸지 않는다.
move_distance(*first, *second, removed_mask)두 카드를 모두 선택하고 Enter를 두 번 누른 뒤에만 next_mask로 바꾼다.
+ 2
+ dfs(next_mask, *second)이 순서가 중요하다. 먼저 카드를 제거해 버리면 Ctrl 이동이 실제 게임 규칙과 달라진다.
예시
첫 번째 예시에서 카드 쌍 제거 순서와 각 쌍의 선택 순서에 따라 Ctrl 이동 결과가 달라진다.
예를 들어 어떤 카드 쌍을 먼저 제거하면 이후 빈 칸이 늘어나므로, Ctrl 이동이 더 멀리 이동할 수 있다. DFS는 가능한 제거 순서를 모두 비교하고, BFS는 각각의 현재 보드 상태에서 실제 최소 이동 횟수를 계산한다.
따라서 두 카드가 남아 있는 순서까지 고려한 최솟값을 구할 수 있다.
시간 복잡도
카드 종류를 K라고 하자. K <= 6이다.
DFS 상태는 제거된 카드 조합과 커서 위치로 이루어진다.
- 제거 상태 수: 최대
2^K - 커서 위치 수: 16
- 한 상태에서 확인할 카드 순서: 최대
2K - BFS 한 번: 보드 칸이 16개이므로
O(1)
제한된 4 x 4 보드와 최대 6개 카드 쌍에서는 충분히 빠르게 동작한다.
- 시간 복잡도:
O(2^K * 16 * K) - 공간 복잡도:
O(2^K * 16)
정리
카드 제거 순서가 Ctrl 이동 경로를 바꾸므로, 제거 순서와 카드 선택 순서를 모두 탐색해야 한다. 제거 상태는 비트마스크로 저장하고, 각 상태의 커서 이동은 BFS로 계산하면 최소 조작 횟수를 구할 수 있다.
