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

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

실패

그리드를 포함한 완전 탐색으로 코드를 구현했다.

결과적으로 코드는 효율성 포함해서 잘 돌아간다. 그러나 greed로 구현하는 방식에 반례가 존재하였다.

a 카드가 a1 $\Rightarrow$ a2 이렇게 탐색하는게 a2 $\Rightarrow$ a1 로 탐색하는 것 보다 순간적으로는 작다고 해도 그 다음 b라는 카드를 탐색할 때, 시작지점이 a2, a1으로 나뉘어진다. 그러나 a1 $\Rightarrow$ a2 $\Rightarrow$ b2 $\Rightarrow$ b1 의 값이 a2 $\Rightarrow$ a1 $\Rightarrow$ b2 $\Rightarrow$ b1 보다 큰 경우가 존재한다.

결국 앞의 결과가 뒤의 계산에도 영향을 미칠 수 있다는 뜻이다.

from queue import deque
from collections import defaultdict
from itertools import permutations as p
from copy import deepcopy
import sys

def solution(board, r, c):
    answer = sys.maxsize
    pair = defaultdict(list)
    
    # 카드(1 ~ 6) 별로 좌표를 전부 확인한다. (순열을 돌리기 위한 작업)
    for y in range(4):
        for x in range(4):
            if board[y][x] != 0:
                pair[board[y][x]].append((y, x))
                
    # 위에서 각 카드 별로 묶여진 좌표들을 순열로 섞는다.
    for order in p(pair.values()):
        s_y, s_x = r, c
        board2 = deepcopy(board)
        temp = 0
        
        # 카드별로 두 장씩 있는데, 순열에 따라 board 형태가 달라지므로
        # 같은 모양의 카드 중 무엇을 먼저 뽑아야하는지도 확인해서 키 입력이 작은 걸 선택한다. 
        for arr in order:
            a = find(board2, s_y, s_x, arr[1][0], arr[1][1]) + find(board2, arr[1][0], arr[1][1], arr[0][0], arr[0][1])
            b = find(board2, s_y, s_x, arr[0][0], arr[0][1]) + find(board2, arr[0][0], arr[0][1], arr[1][0], arr[1][1])
            
            if a > b:
                s_y, s_x = arr[1][0], arr[1][1]
            else:
                s_y, s_x = arr[0][0], arr[0][1]
                
            board2[arr[1][0]][arr[1][1]] = 0
            board2[arr[0][0]][arr[0][1]] = 0
            
            temp += min(a, b) + 2
        answer = min(answer, temp)
        
    return answer


# bfs로 시작(s_y, s_x)과 끝(e_y, e_x)이 주어지면 시작에서 끝까지 가는 최단경로를 찾는다.
def find(board, s_y, s_x, e_y, e_x):
    que = deque([(s_y, s_x, 0)])
    cand = ((1, 0), (0, -1), (-1, 0), (0, 1))
    confirm = {(s_y, s_x)}
    
    while que:
        y, x, cnt = que.popleft()
        
        if y == e_y and x == e_x:
            return cnt
            
        for dy, dx in cand:
            y1, x1 = y, x
            if 0 <= y + dy < 4 and 0 <= x + dx < 4 and (y + dy, x + dx) not in confirm:
                que.append((y + dy, x + dx, cnt + 1))
                confirm.add((y + dy, x + dx))
                
            while 0 <= y1 + dy < 4 and 0 <= x1 + dx < 4:
                y1 += dy
                x1 += dx
                if board[y1][x1] != 0:
                    break
                    
            if (y1, x1) not in confirm:
                que.append((y1, x1, cnt + 1))
                confirm.add((y1, x1))

---

성공

모든 경우를 확인하는 순열을 dfs를 통해 직접 구현하였다.

from queue import deque
from collections import defaultdict
from copy import deepcopy
import sys

def solution(board, r, c):
    pair = defaultdict(list)
    
    for y in range(4):
        for x in range(4):
            if board[y][x] != 0:
                pair[board[y][x]].append((y, x))
                
    return p(list(pair.keys()), (r, c), board, pair)


def find(board, s, e):
    s_y, s_x , e_y, e_x = *s, *e
    que = deque([(s_y, s_x, 0)])
    cand = ((1, 0), (0, -1), (-1, 0), (0, 1))
    confirm = {(s_y, s_x)}
    
    while que:
        y, x, cnt = que.popleft()
        
        if y == e_y and x == e_x:
            board[y][x] = 0
            return cnt
            
        for dy, dx in cand:
            y1, x1 = y, x
            if 0 <= y + dy < 4 and 0 <= x + dx < 4 and (y + dy, x + dx) not in confirm:
                que.append((y + dy, x + dx, cnt + 1))
                confirm.add((y + dy, x + dx))
                
            while 0 <= y1 + dy < 4 and 0 <= x1 + dx < 4:
                y1 += dy
                x1 += dx
                if board[y1][x1] != 0:
                    break
                    
            if (y1, x1) not in confirm:
                que.append((y1, x1, cnt + 1))
                confirm.add((y1, x1))


def p(arr, s, board, pair):
    if not arr:
        return 0

    answer = sys.maxsize
    
    for idx, num in enumerate(arr):

        a = find(board, s, pair[num][0]) + find(board, pair[num][0], pair[num][1]) + p(arr[:idx] + arr[idx + 1:], pair[num][1], board, pair)
        board[pair[num][0][0]][pair[num][0][1]] = num
        board[pair[num][1][0]][pair[num][1][1]] = num
        
        b = find(board, s, pair[num][1]) + find(board, pair[num][1], pair[num][0]) + p(arr[:idx] + arr[idx + 1:], pair[num][0], board, pair)
        board[pair[num][0][0]][pair[num][0][1]] = num
        board[pair[num][1][0]][pair[num][1][1]] = num
        
        answer = min(min(a, b) + 2, answer)
    
    return answer