Programmers - 카드 짝 맞추기

문제 링크

모든 가능한 순서를 다 시뮬레이션 해야 한다.

ex) 3장의 카드 짝이 있는 경우 [1,2,3],[2,1,3] ... [3,2,1] 로 모든 찾을 카드 순서를 정하고
    같은 번호 카드를 각각 A,B 라고 할 때, A->B로 가는 방법, B->A로 가는 경우를 모두 시뮬레이션해야 함.

나는 진행할때 찾을 카드를 0으로 만들고 나서 이동비용을 계산했는데
cost()를 구현할때 이를 고려하지 않아서 문제 푸는 시간이 오래걸렸다.
ctrl + 방향키 로 이동할때 중간지점이 목적지일 경우를 조건에 추가해서 문제를 해결할 수 있었다.

from collections import deque
from itertools import permutations


positions = [[] for _ in range(7)]


def solution(board, r, c):
    global positions

    card_count = 0
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                positions[board[i][j]].append((i, j))
                card_count = max(card_count, board[i][j])

    li = [i for i in range(1, card_count+1)]
    answer = 987654321

    for sequence in permutations(li):
        copied = copy_board(board)
        answer = min(answer, process(copied, (r, c), sequence))

    return answer


def copy_board(board):
    copied = []
    for row in board:
        copied.append(row[:])
    return copied


def process(board, start, sequence):
    global positions
    if len(sequence) == 0:
        return 0

    next = sequence[0]
    p1 = positions[next][0]
    p2 = positions[next][1]

    # Enter 포함
    (ax, ay) = p1
    (bx, by) = p2

    board[ax][ay] = 0
    board[bx][by] = 0

    result1 = cost(board, start, p1) + cost(board, p1, p2) + \
        2 + process(board, p2, sequence[1:])

    result2 = cost(board, start, p2) + cost(board, p2, p1) + \
        2 + process(board, p1, sequence[1:])
    board[ax][ay] = next
    board[bx][by] = next
    return min(result1, result2)


def cost(board, fr, to):
    q = deque()
    visit = [[False for _ in range(4)] for __ in range(4)]
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q.append(fr)
    visit[fr[0]][fr[1]] = True

    def can_visit(x, y):
        if not (0 <= x < 4 and 0 <= y < 4):
            return False
        return not visit[x][y]

    count = 0

    while len(q) > 0:
        for _ in range(len(q)):
            (x, y) = q.popleft()
            if (x, y) == to:
                return count

            for (dx, dy) in moves:
                # 이동
                ax = x + dx
                ay = y + dy
                if can_visit(ax, ay):
                    visit[ax][ay] = True
                    q.append((ax, ay))
                # ctrl + 이동
                # 0이 아닌게 나올때까지 이동
                while 0 <= ax < 4 and 0 <= ay < 4 and board[ax][ay] == 0:
                    ax += dx
                    ay += dy
                    if (ax, ay) == to:
                        q.append(to)

                if not (0 <= ax < 4 and 0 <= ay < 4):
                    ax -= dx
                    ay -= dy
                if can_visit(ax, ay):
                    visit[ax][ay] = True
                    q.append((ax, ay))
        count += 1
    return 0