[프로그래머스] 카드 짝 맞추기 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/72415

프로그래머스

---

📍 Problem

4x4 크기의 보드에, 짝이 있는 카드가 주어진다. 카드를 선택해 뒤집고 짝 카드를 찾아 뒤집으면 해당 카드들이 사라진다. 카드는 커서를 이용해 선택할 수 있으며, 키를 조작해 커서를 이동시킬 수 있다. 모든 카드를 화면에서 사라지게 하는 최소 키 조작 횟수를 구한다. 

커서는 [Ctrl] 키와 방향키에 의해 이동된다. 
- 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동 (조작 횟수 1)
- [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동 (해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동) (조작 횟수 1)

커서가 위치한 카드는 [Enter] 키로 뒤집을 수 있다. (조작 횟수 1)

board는 4x4 크기의 2차원 배열로, 각 원소는 0 이상 6이하의 자연수이다. 

- 0은 카드가 제거된 빈 칸

- 1~6 자연수는 2개씩 들어 있으며 같은 그림의 카드를 의미한다. 

r, c는 커서의 최초 위치이다.  

---

💡 Solution

각 카드의 짝을 찾는 BFS를 이용해 전체 카드를 뒤집는 최소 비용을 구할 수 있다. 카드를 선택해 뒤집으면, 무조건 최소비용으로 짝에 해당하는 카드를 찾아 뒤집는다고 가정한다. 목표 좌표에 도착할 때까지 방향키 조작, [Ctrl] + 방향키 조작 총 8가지 행동을 수행하는 BFS를 구현한다. 

 

또한 어떤 카드를 먼저 선택하냐에 따라 비용이 달라지므로, 카드를 선택하는 조합을 구해야한다.  

예를 들어 카드가 3개 일 때, 카드 종류가 [1, 2, 3] 이라고 가정하면, 카드 종류를 선택하는 순서는 3P3 = 3! 가지이다.

 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]   # 카드 종류만 고려했을 때

이때 주의해야할 점은 카드는 종류 별로 2장씩 있으므로, 카드 종류마다 어떤 카드를 먼저 선택할지도 고려해야한다. 따라서 카드를 선택하는 순서에 대한 경우의 수는  3P3 x 2^3 이다. 

[1, 1', 2, 2', 3, 3'], [1', 1, 2, 2', 3, 3'], [1, 1', 2', 2, 3, 3'], [1, 1', 2, 2', 3', 3], .... [1', 1, 2', 2, 3', 3]  # [1, 2, 3] 카드 순서에 대해

하나의 경우의 수 [1, 1', 2, 2', 3, 3'] 에 대해 BFS는 6번을 수행해야한다.

(시작 위치 -> 1), (1 -> 1'), (1' -> 2), (2 -> 2'), (2' -> 3), (3 -> 3')

따라서 카드 종류 갯수 n에 대해 nPn x 2^n의 탐색 순서가 존재하고, 각 순서마다 2n번의 BFS를 수행하게 된다. 

---

구현은 permutations 와 비트마스크를 통해 카드를 탐색하는 모든 조합을 만든후, 각 조합에 대해 BFS를 통해 최소 비용을 구해주었다 (def move_by_order()). (BFS 에서 [Enter]조작을 고려하지 않는데, [Enter] 조작은 무조건 2n 번이므로 최종 결과에 추가해주었다.)

 

이때 모든 경우를 BFS를 수행하면 시간초과가 나는데, 이를 해결하기 위해 이미 탐색한적 있는 BFS는 캐싱해 두고 재사용한다. 캐싱은 순열로 정해진 같은 카드 순서에 대해 유효하다.  

 

ex.  위 예시에서 본 다음 경우의 수에서, 1 -> 1' 는 항상 같은 비용이 들기 때문에 캐싱이 가능하다.

[1, 1', 2, 2', 3, 3'], [1', 1, 2, 2', 3, 3'], [1, 1', 2', 2, 3, 3'], [1, 1', 2, 2', 3', 3], .... [1', 1, 2', 2, 3', 3]  # [1, 2, 3] 카드 순서에 대해

다른 카드 순서 [2, 2', 1, 1', 3, 3'] 의 1->1' 비용은 보드 상태에 따라 앞 예제의 1-> 1' 비용과 달라질 수 있으므로 카드 순서에 따라 cache dict를 초기화 해주어야한다. 

import copy
from collections import deque, defaultdict
from itertools import permutations

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def out_of_bound(x, y):
    if not 0 <= x < 4 or not 0 <= y < 4:
        return True
    else:
        return False


# 방향키 상,하,좌,우 => 1칸 이동 (cost 1)
# ctrl + 상,하,좌,우 => 누른 키 방향에 있는 가장 가까운 카드로 이동
#                      해당 방향에 카드가 하나도 없으면 그 방향에 가장 마지막 칸으로 이동
def bfs(board, source, target, current_min):
    q = deque()
    q.append(source)
    visited = [[0]* 4 for _ in range(4)]
    visited[source[0]][source[1]] = 0 
    while len(q) > 0:
        x, y = q.popleft()

        if visited[x][y] > current_min:
            return current_min

        if (x, y) == target:
            return visited[x][y]

        # 방향키
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if out_of_bound(nx, ny):
                continue
            if visited[nx][ny] > 0:
                continue
            visited[nx][ny] = visited[x][y] + 1
            q.append((nx, ny))

        # ctrl + 방향키
        for dx, dy in directions:
            nx = x
            ny = y
            while True:
                if out_of_bound(nx + dx, ny + dy):  # 더 이상 이동 불가
                    break
                else:
                    nx += dx
                    ny += dy
                if board[nx][ny] != 0:
                    # 카드를 만나면 이동
                    if visited[nx][ny] == 0:
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))
                    break
            if (nx, ny) != (x, y):
                # 끝 칸 이동
                if visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))


def solution(board, r, c):
    loc = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] == 0:
                continue
            loc[board[i][j]].append((i, j))
    n_card = len(loc.keys())  # 카드 종류 갯수

    permute = list(permutations(loc.keys(), n_card))
    min_move = float('inf')

    orders = []
    for p in permute:
        cache = {}
        for b in range(1 << n_card):
            order = []
            for j in range(n_card):
                card = loc[p[j]]
                if b & (1 << j) > 0:
                    order.append(card[0])
                    order.append(card[1])
                else:
                    order.append(card[1])
                    order.append(card[0])
            cost = move_by_order(board, r, c, order, min_move, cache)
            min_move = min(cost, min_move)

    return  min_move + (n_card*2)  # enter 조작 포함


def move_by_order(board, r, c, order, current_min, cache):
    board = copy.deepcopy(board)
    cost = 0
    cursor = (r, c)
    for i in range(len(order)):
        if cost >= current_min:
            return current_min
        board[cursor[0]][cursor[1]] = 0  # 카드 뒤집기
        if (cursor, order[i]) in cache:  # BFS를 수행한 적있는 경우의 수는 캐싱
            _cost = cache[(cursor, order[i])]
        else:
            _cost = bfs(board, cursor, order[i], current_min)
            cache[(cursor, order[i])] = _cost
        cost += _cost 
        cursor = order[i]
    return cost


if __name__ == '__main__':
    board = [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]
    r = 0
    c = 1
    res = solution(board, r, c)
    print(res)