# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:72415

# 카드 짝 맞추기

ps
링크https://programmers.co.kr/learn/courses/30/lessons/72415
출처프로그래머스
문제 번호72415
문제명카드 짝 맞추기
레벨Level 3
분류

구현, BFS, DP

시간복잡도O(n^2 * 2^n)
인풋사이즈n<=6
사용한 언어Python
해결날짜2021/01/29
출처2021 KAKAO BLIND RECRUITMENT

## 풀이

• 카드의 종류가 작아서 어떻게 풀든 풀리기는 풀린다.
• 최대 n종류의 카드를 지우는 방법의 순서는 n! 가지. 그리고 각 카드 종류별로 두장의 카드가 있으니까, 어느쪽을 먼저 선택할지에 따라서 두종류의 방법이 있다. 그러면 이동하는 경로의 종류는 (2^n)*(n!) 가지이다. 각 경로는 2*n개의 카드를 선택해야 한다. 한번 선택하기 위해 이동할때마다 BFS가 필요하다. BFS는 노드 갯수가 4*4=16으로 정해져 있으니까 그냥 상수처리 한다고 해도 총 시간 복잡도는 O(2^n * n! * 2n). 복잡도는 크기만.. n이 최대 6이므로 풀리긴 풀린다.
• DP를 이용하면 좀더 최적화가 가능하다. n개의 점을 최소 비용으로 방문하는 순서이므로 TSP 문제를 DP로 푸는 것과 비슷하다.
• s를 남은 카드의 집합 {c1, c2,.., cn}이라 하고, pos∈{p[c1], p[c1], p[c2], p[c2], … p[cn], p[cn]}는 어떤 카드가 있는 위치라고 한 뒤, dp[s][pos]를 pos에서 시작해서 s를 다 제거하는 데 필요한 키 입력 횟수라고 정의하자.
• \begin{aligned} dp[s][p[c0]] = \min_i(\min(&d(p[c0], p[c0])+d(p[c0], p[ci]) + dp[s-\{c0\}][p[ci]], \\ & d(p[c0], p[c0])+d(p[c0], p[ci]) + dp[s-\{c0\}][p[ci]])) \end{aligned}
• dp[s][pos] 를 계산하려면 (|s|-1)*2 가지 중에서 최소값을 구해야 하므로 O(|s|)=O(n)이 필요하다. s의 가짓수는 총 2^n개. pos의 가짓수는 O(n)개. 그러면 n*2^n개의 셀에대해서 계산해야하고, 한번 계산은 O(n)이니까 O(n^2 * 2^n)
• 다만 구현이 꽤나 귀찮다. 특히 특정 셀로 이동하는데 필요한 최소 입력 횟수를 구하기 위해서 BFS를 사용해야 하는데, 그냥 이동, Ctrl을 누르고 이동, Ctrl을 누르고 이동했을때 그 방향에 다른 카드가 없는 경우까지 고려하려면 구현이 길어질 수밖에 없다.
• 그리고 얼핏 a에서 b로 갈때랑, b에서 a로 갈때의 최소 키입력 횟수가 똑같다고 실수하기 쉬운데, 두 경우는 키입력 횟수가 다를 수 있다.
• 다행히 DP를 구현하는 것은, 자연수 인덱싱 가능한 DP 테이블을 만들기위해 S를 비트셋으로 표현하고 하는 귀찮은 작업을 하는 대신, 그냥 S 자체를 튜플로 바꾼 것을 키로 사용하는 dict 구조로 테이블을 만들려고 했고, 그나마도 테이블을 명시적으로 만드는 대신에 재귀함수에 functools.lru_cache을 붙이는 것으로 처리했더니 좀 간단하게 처리되었다.

## 코드

"""Solution code for "Programmers 72415. 카드 짝 맞추기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72415
- Solution link: http://www.teferi.net/ps/problems/programmers/72415
"""

import collections
import functools

INF = float('inf')

def solution(board, r, c):

def next_pos(pos, cards):
r, c = pos
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < 4 and 0 <= nc < 4:
yield nr, nc
for i in range(1, 5):
nr, nc = r + dr * i, c + dc * i
if not (0 <= nr < 4 and 0 <= nc < 4):
yield nr - dr, nc - dc
break
elif board[nr][nc] in cards:
yield nr, nc
break

@functools.lru_cache(maxsize=None)
def bfs(start, target, cards):
if start == target:
return 0
visited = set()
queue = collections.deque([(start, 0)])
while queue:
cur, dist = queue.popleft()
for next_ in next_pos(cur, cards):
if next_ == target:
return dist + 1
if next_ not in visited:
visited.add(next_)
queue.append((next_, dist + 1))
return INF

@functools.lru_cache(maxsize=None)
def min_dist_rec(cur_pos, cards):
if not cards:
return 0
min_dist = INF
for card_to_clear in cards:
pos1, pos2 = pos[card_to_clear]
next_cards = tuple(card for card in cards if card != card_to_clear)
dist1 = (bfs(cur_pos, pos2, cards) + bfs(pos2, pos1, cards) +
min_dist_rec(pos1, next_cards))
dist2 = (bfs(cur_pos, pos1, cards) + bfs(pos1, pos2, cards) +
min_dist_rec(pos2, next_cards))
min_dist = min(min_dist, dist1, dist2)
return min_dist

pos = collections.defaultdict(list)
for r_, row in enumerate(board):
for c_, card in enumerate(row):
if card != 0:
pos[card].append((r_, c_))
cards = tuple(pos)
return len(cards) * 2 + min_dist_rec((r, c), cards)

## 토론

댓글을 입력하세요:
K​ V E​ J K

ps/problems/programmers/72415.txt · 마지막으로 수정됨: 2021/01/30 15:21 저자 teferi

### 문서 도구 