[プログラマー]ペアリングカード

https://programmers.co.kr/learn/courses/30/lessons/72415
失敗
グリッドを含む完全なナビゲーションによりコードを実現した.
その結果、効率を含めてコードがうまく動作します.しかし、貪欲で表現する方法には反例がある.
aカードがa 1Rightarow.a 2のように探索されるのはa 2Rightarow.a 1探索の瞬間よりも小さいとしても、次のbというカードを探索する際に、始点はa 2、a 1に分けられる.ただし、a 1Rightarrowa 2Rightarrowb 1の値は、a 2Rightarrowa 1]b 2\Rightarrowb 1がb 1より大きい場合に存在する.
これは,前の結果も後の計算に影響を及ぼすことを意味する.

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