카드 짝 맞추기

• 카드의 종류가 작아서 어떻게 풀든 풀리기는 풀린다.
• 최대 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][0], p[c1][1], p[c2][0], p[c2][1], … p[cn][0], p[cn][1]}는 어떤 카드가 있는 위치라고 한 뒤, dp[s][pos]를 pos에서 시작해서 s를 다 제거하는 데 필요한 키 입력 횟수라고 정의하자.
  • $ \begin{aligned} dp[s][p[c0][0]] = \min_i(\min(&d(p[c0][0], p[c0][1])+d(p[c0][1], p[ci][0]) + dp[s-\{c0\}][p[ci][0]], \\ & d(p[c0][0], p[c0][1])+d(p[c0][1], p[ci][1]) + dp[s-\{c0\}][p[ci][1]])) \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)