[PRO] 카드 짝 맞추기

다음 풀이는 56.7 / 100.0이다. 일부 테스트 케이스는 틀리고, 일부는 시간초과가 났다.

from collections import defaultdict, deque
from itertools import permutations, product

directions = [(1,0),(0,1),(-1,0),(0,-1)] # ctrl 안눌렀을때

def is_valid(x,y):
    if 0<=x<4 and 0<=y<4:
        return True
    return False
        

def move_count(board, now_point, end_point):
    
    # BFS로 최단경로 찾기
    x,y = now_point
    visited = [[False]*4 for _ in range(4)] # 방문여부 초기화
    visited[x][y] = True
    
    q = deque()
    q.append((x,y,0))
    now_min_cnt = float('inf')
    while q:
        x,y,cnt = q.popleft()
        
        if (x,y) == end_point: # 도달
            return cnt+1 # 마지막 ENTER까지
        
        for dx, dy in directions: # 4방향 갈 수 있는 곳
            next_x = x + dx
            next_y = y + dy
            
            while is_valid(next_x, next_y) and board[next_x][next_y]==0:
                next_x += dx
                next_y += dy
            
            if not is_valid(next_x, next_y):
                next_x -= dx
                next_y -= dy
                
            if not visited[next_x][next_y]:
                q.append((next_x, next_y, cnt+1)) # 큐에 추가
                visited[next_x][next_y] = True
            
            # 초기화
            next_x = x + dx
            next_y = y + dy
            one_step_count = cnt
            while is_valid(next_x, next_y) and board[next_x][next_y]==0:
                q.append((next_x, next_y, one_step_count+1))
                next_x += dx
                next_y += dy
                one_step_count += 1
    
    return 0 # 도달을 못하는 경우?


def solution(board, r, c):
    card_dict = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j]:
                card_dict[board[i][j]].append((i,j))
    
    # 경로 모든 경우
    paths = []
    for pair_list in permutations(card_dict.values(), len(card_dict)): # 6P6=720
        for idx_bool_list in product([False, True], repeat=len(card_dict)): # 2**6=64
            now_path = [(r,c)]
            for pair, idx_bool in zip(pair_list, idx_bool_list): # 6
                if idx_bool:
                    pair.reverse()
                now_path.extend(pair)
            paths.append(now_path)
    
    print(len(paths))
    # 각 경로마다 조작 횟수 계산
    answer = float('inf')
    for path in paths:
        copied_board = [row[:] for row in board] # board 새로 생성
        now_count = 0 # 초기 ENTER?
        for i in range(len(path)-1):
            # for row in copied_board:
            #     print(row)
            # print(path[i],path[i+1])
            
            now_count += move_count(copied_board, path[i], path[i+1]) # 최소이동경로의 횟수
            copied_board[path[i][0]][path[i][1]] = 0 # 제거
            copied_board[path[i+1][0]][path[i+1][1]] = 0 # 제거
            #print(now_count)
        answer = min(answer, now_count)
        #break
        #return now_count
    
    return answer