title: "[프로그래머스] 카드 짝 맞추기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/72415"
description: "프로그래머스 Level 3 문제 [카드 짝 맞추기]의 풀이를 정리합니다."
import itertools
from math import inf
from copy import deepcopy
from collections import deque, defaultdict
def solution(board, r, c):
initr, initc = r, c
R, C = len(board), len(board[0])
# 카드 종류가 6개밖에 안 됩니다.
# 탐색 순서의 모든 경우의 수는 최대 2^6 x 6! = 46080 가지밖에 없습니다.
# 브루트포스로 해결 가능해보입니다.
# 1부터 maxval 까지 종류의 카드가 있습니다.
maxval = max(board[r][c] for r in range(R) for c in range(C))
# 문제 해결을 위한 함수들을 작성해봅시다.
# (r1, c1)에서 (r2, c2)로 최소 조작으로 이동할 때 조작 횟수
# BFS로 계산하면 됩니다.
def move(r1, c1, r2, c2, B):
# BFS가 필요 없는 자명한 위치 관계들은 따로 처리해주는 식으로
# 시간 최적화를 조금 해줍니다. 이래야 10초 이내로 빡빡하게 통과...
if r1 == r2:
cmin, cmax = min(c1, c2), max(c1, c2)
if cmax - cmin == 1:
return 1
elif cmax - cmin == 2 and B[r1][cmin+1] == 0:
return 1
elif cmax - cmin == 3 and B[r1][cmin+1] == 0 and B[r1][cmin+2] == 0:
return 1
if c1 == c2:
rmin, rmax = min(r1, r2), max(r1, r2)
if rmax - rmin == 1:
return 1
elif rmax - rmin == 2 and B[rmin+1][c1] == 0:
return 1
elif rmax - rmin == 3 and B[rmin+1][c1] == 0 and B[rmin+2][c1] == 0:
return 1
q, vis = deque(), set()
q.append( (0, r1, c1) )
vis.add( (r1, c1) )
while q:
d, r, c = q.popleft()
if r == r2 and c == c2:
return d
# 상하좌우 1칸씩
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
if 0 <= r+dr < R and 0 <= c+dc < C:
if (r+dr, c+dc) not in vis:
q.append( (d+1, r+dr, c+dc) )
vis.add( (r+dr, c+dc) )
# 1. 위쪽으로 이동
if dr == -1 and dc == 0 and B[r+dr][c+dc] == 0:
nr, nc = r+dr, c+dc
while nr > 0 and B[nr][nc] == 0:
nr -= 1
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis:
q.append( (d+1, nr, nc) )
vis.add( (nr, nc) )
# 2. 오른쪽으로 이동
elif dr == 0 and dc == 1 and B[r+dr][c+dc] == 0:
nr, nc = r+dr, c+dc
while nc < C-1 and B[nr][nc] == 0:
nc += 1
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis:
q.append( (d+1, nr, nc) )
vis.add( (nr, nc) )
# 3. 왼쪽으로 이동
elif dr == 0 and dc == -1 and B[r+dr][c+dc] == 0:
nr, nc = r+dr, c+dc
while nc > 0 and B[nr][nc] == 0:
nc -= 1
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis:
q.append( (d+1, nr, nc) )
vis.add( (nr, nc) )
# 4. 아래쪽으로 이동
elif dr == 1 and dc == 0 and B[r+dr][c+dc] == 0:
nr, nc = r+dr, c+dc
while nr < R-1 and B[nr][nc] == 0:
nr += 1
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in vis:
q.append( (d+1, nr, nc) )
vis.add( (nr, nc) )
# 모든 경우의 수를 탐색해봅니다.
# order: 카드 종류를 탐색하는 순서
# cards[카드 종류] : 카드 위치들
cards = defaultdict(list)
for r in range(R):
for c in range(C):
if board[r][c] != 0:
cards[board[r][c]].append((r, c))
mn = inf
for order in itertools.permutations(range(1, maxval + 1)):
# mask: 먼저 탐색된 카드를 먼저 볼 것인지 (0), 아닌지 (1)
for mask in itertools.product([0, 1], repeat=maxval):
# 이하가 탐색의 한 가지 경우의 수입니다.
skip = False
B = [[row[c] for c in range(C)] for row in board]
nmove, path = 0, []
# 각각의 카드를 찾아서 위치를 기록해둡니다.
for val, reverse in zip(order, mask):
cardpos = cards[val][::-1] if reverse else cards[val]
path.extend(cardpos)
# 이제 path 순서대로 따라가면서 이동하면 됩니다.
currr, currc = initr, initc
nmove = 0
for i, (r, c) in enumerate(path, 1):
nmove += move(currr, currc, r, c, B)
# (최적화) 지금까지의 최솟값보다 크면 탐색을 멈춥니다.
if nmove >= mn:
skip = True
break
currr, currc = r, c
B[r][c] = 0
if skip:
continue
if nmove < mn:
mn = nmove
return mn + maxval * 2
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges