카카오 기출 - 카드 뒤집기

from itertools import permutations

def movePosition(start, end, board):
    startY, startX = start
    endY, endX = end
    cnt = 0

    # 가로먼저 이동
    if startX < endX:
        if endX - startX == 1:
            cnt += 1
        elif endX - startX == 2:
            if board[startY][startX + 1] != 0:
                cnt += 2
            elif endX == 3:
                cnt += 1
            elif board[startY][endX] != 0:
                cnt += 1
            elif board[startY][endX] == 0:
                cnt += 2
        elif endX - startX == 3:
            for i in range(1, 4):
                if board[startY][i] != 0:
                    cnt += 1
            if board[startY][3] == 0:
                cnt += 1

    elif startX > endX:
        if startX - endX == 1:
            cnt += 1
        elif startX - endX == 2:
            if board[startY][endX + 1] != 0 :
                cnt += 2
            elif endX == 0 :
                cnt += 1
            elif board[startY][endX] != 0 :
                cnt += 1
            elif board[startY][endX] == 0 :
                cnt += 2
        elif startX - endX == 3:
            for i in range(2, -1, -1):
                if board[startY][i] != 0:
                    cnt += 1
            if board[startY][0] == 0:
                cnt += 1
    # 그다음에 세로이동
    if startY < endY:
        if endY - startY == 1:
            cnt += 1
        elif endY - startY == 2:
            if board[startY+1][endX] != 0:
                cnt += 2
            elif endY == 3:
                cnt += 1
            elif board[endY][endX] != 0:
                cnt += 1
            elif board[endY][endX] == 0:
                cnt += 2
        elif endY - startY == 3:
            for i in range(1, 4):
                if board[i][endX] != 0:
                    cnt += 1
            if board[3][endX] == 0:
                cnt += 1

    elif startY > endY:
        if startY - endY == 1:
            cnt += 1
        elif startY - endY == 2:
            if board[endY + 1][endX] != 0 :
                cnt += 2
            elif endY == 0 :
                cnt += 1
            elif board[endY][endX] != 0 :
                cnt += 1
            elif board[endY][endX] == 0:
                cnt += 2
        elif startY - endY == 3:
            for i in range(2, -1, -1):
                if board[i][endX] != 0:
                    cnt += 1
            if board[0][endX] == 0:
                cnt += 1

    cnt2 = 0
    # 이번엔 세로먼저 이동
    if startY < endY:
        if endY - startY == 1:
            cnt2 += 1
        elif endY - startY == 2:
            if board[startY+1][startX] != 0:
                cnt2 += 2
            elif endY == 3:
                cnt2 += 1
            elif board[endY][startX] != 0:
                cnt2 += 1
            elif board[endY][startX] == 0:
                cnt2 += 2
        elif endY - startY == 3:
            for i in range(1, 4):
                if board[i][startX] != 0:
                    cnt2 += 1
            if board[3][startX] == 0:
                cnt2 += 1

    elif startY > endY:
        if startY - endY == 1:
            cnt2 += 1
        elif startY - endY == 2:
            if board[endY + 1][startX] != 0 :
                cnt2 += 2
            elif endY == 0 :
                cnt2 += 1
            elif board[endY][startX] != 0 :
                cnt2 += 1
            elif board[endY][startX] == 0:
                cnt2 += 2
        elif startY - endY == 3:
            for i in range(2, -1, -1):
                if board[i][startX] != 0:
                    cnt2 += 1
            if board[0][startX] == 0:
                cnt2 += 1

    # 그다음 가로 이동
    if startX < endX:
        if endX - startX == 1:
            cnt2 += 1
        elif endX - startX == 2:
            if board[endY][startX + 1] != 0:
                cnt2 += 2
            elif endX == 3:
                cnt2 += 1
            elif board[endY][endX] != 0:
                cnt2 += 1
            elif board[endY][endX] == 0:
                cnt2 += 2
        elif endX - startX == 3:
            for i in range(1, 4):
                if board[endY][i] != 0:
                    cnt2 += 1
            if board[endY][3] == 0:
                cnt2 += 1

    elif startX > endX:
        if startX - endX == 1:
            cnt2 += 1
        elif startX - endX == 2:
            if board[endY][endX + 1] != 0 :
                cnt2 += 2
            elif endX == 0 :
                cnt2 += 1
            elif board[endY][endX] != 0 :
                cnt2 += 1
            elif board[endY][endX] == 0 :
                cnt2 += 2
        elif startX - endX == 3:
            for i in range(2, -1, -1):
                if board[endY][i] != 0:
                    cnt2 += 1
            if board[endY][0] == 0:
                cnt2 += 1
    # 더 짧은거 리턴
    return cnt if cnt < cnt2 else cnt2

import copy
def solution(board, r, c):
    answer = 1000000000
    
    dict = {}
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0 :
                if board[i][j] not in dict:
                    dict[board[i][j]] = [[i,j]]
                else :
                    dict[board[i][j]].append([i, j])

    nums = list(dict.keys())

    for order in permutations(nums):
        arr = copy.deepcopy(board)
        cur = [r, c]
        cumul = 0
        for i in order:
            # a 번 카드는 두장 둘 중에 현재 위치에서 더 가까운건?
            p1 = movePosition(cur, dict[i][0], arr)
            p2 = movePosition(cur, dict[i][1], arr)
            # 더 가까운 애에서 나머지 한장으로 이동
            if p1 < p2 :
                cur = dict[i][1]
                cumul += p1 + movePosition(dict[i][0], dict[i][1], arr)
            else :
                cur = dict[i][0]
                cumul += p2 + movePosition(dict[i][1], dict[i][0], arr)
            arr[dict[i][0][0]][dict[i][0][1]] = 0
            arr[dict[i][1][0]][dict[i][1][1]] = 0

        if cumul < answer:
            answer = cumul
    return answer + len(nums) * 2

print(solution(		[   [1, 0, 0, 3],
                        [2, 0, 0, 0],
                        [0, 0, 0, 2],
                        [3, 0, 1, 0]], 1, 0), 14)

맞아서 기분은 좋은데 거리 구하는 함수가 무지성이라 찝찝하다 ㅋㅋㅋㅋㅋㅋㅋ 한시간 반? 정도 걸린거 같은데...  코드가 길어지면서 이건 무조건 시간초과다... 했지만 칸이 4*4 라서 시간초과가 날 수가 없는 문제같다. 젤 오래걸린 것도 30ms가 안되기도 하고 . 어쨌든 더 좋은 코드가 생각나면 고쳐봐야겠다

문제를 풀면서 느낀건 만약 5*5 였으면 카드 이동하는 경우의 수가 훨씬 복잡해져서 4*4는 카카오 나름의 배려가 아닌가 싶다.