[Python] 프로그래머스 level3 카드 짝 맞추기

programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

풀이 방법

• 정답률이 0.95%인 6번 문제였다..... 어쩐지 어렵더라
• 처음 잘못 생각했던 것 : 나는 2번 지우고 가장 가까운 다음 카드로 가서 그거 지우고, 지운 후 위치에서 가장 가까운데 가서 또 지우고,... 를 반봅했다. 가장 가까운데를 찾아다니면 최소 비용이 나올거라 생각했다. -> X
• 모든 순열에 대해서 생각해 줘야한다. 1, 2, 3번 카드가 있다면 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-2-1, 3-1-2 이렇게 모든 순서로 방문하는 비용을 더해줘야 한다!
• 모든 순열에 대해서 고려해주기 위해서 iteratools의 permutation을 사용했다. (브루트포스로 순열도 구해줄 수 있지만 귀찮아서 그냥 permutations썼다. ) -> permutations는 순열을 구해주는 함수이다.
• 모든 순열에 대해 돌면서, 순서대로 카드를 지워 나간다.
• 1번 카드를 지우는 최소 비용 = 현재 위치에서 가까운 1번 카드로 이동 + 1번 카드 지우고 + 다른 1번 카드로 이동 + 카드 지우기 
• bfs를 이용해 시작 좌표부터 끝 좌표까지 이동하는데 드는 최소 비용을 return하는 함수를 만든다. 

전체 코드

from collections import deque
from itertools import permutations
from copy import deepcopy

board = []
def ctrl_move(r, c, k, t):
    global board
    cr, cc = r, c
    while True:
        nr = cr + k
        nc = cc + t
        if not (0<=nr<4 and 0<=nc<4):
            return cr, cc
        if board[nr][nc] != 0:
            return nr, nc
        cr = nr
        cc = nc

def bfs(start, end):
    r, c = start
    find_r, find_c = end
    queue = deque()
    queue.append((r, c, 0))
    visited = [[0]*4 for _ in range(4)]
    move = [(0,-1),(0,1),(-1,0),(1,0)]
    while queue:
        r, c, temp = queue.popleft()
        if visited[r][c]: continue
        visited[r][c] = 1
        if r == find_r and c == find_c:
            return temp
        for k, t in move:
            cr = k+r
            cc = c+t
            if 0<=cr<4 and 0<=cc<4:
                queue.append((cr,cc, temp+1))
            cr, cc = ctrl_move(r, c, k, t)
            queue.append((cr, cc, temp+1))
    return -1

def solution(input_board, sr, sc):
    global board
    board = input_board
    location = [[] for _ in range(7)]
    nums = []
    for i in range(4):
        for j in range(4):
            if board[i][j]:
                if board[i][j] not in nums: nums.append(board[i][j])
                location[board[i][j]].append((i, j))
    per = list(permutations(nums, len(nums))) # 순열
    answer = float('inf')
    for i in range(len(per)):
        board = deepcopy(input_board) # 지웠던 곳 다시 채우기
        cnt = 0
        r, c = sr, sc
        for j in per[i]:
            left = bfs((r, c), location[j][0])
            right = bfs((r, c), location[j][1])
            if left < right:
                cnt += left
                cnt += bfs(location[j][0], location[j][1])
                r, c = location[j][1]
            else:
                cnt += right
                cnt += bfs(location[j][1], location[j][0])
                r, c = location[j][0]
            board[location[j][0][0]][location[j][0][1]] = 0 # 카드 지우기
            board[location[j][1][0]][location[j][1][1]] = 0 # 카드 지우기
            cnt += 2 # enter
        answer = min(answer, cnt)
    return answer