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

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

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

 

너무 힘든 문제였다.

 

예를 들어 캐릭터가 1, 2, 3이 있다고 하자.

그럼 card = {1 : [1의 좌표], 2 : [2의 좌표], 3 : [3의 좌표]}

 

1의 좌표가 (0, 0), (3, 2) 라고 한다면, (0, 0) -> (3, 2) 또는 (3, 2) -> (0, 0) 을 생각해줘야 한다.

card[i] = list(permutations(card[1])) 로 다시 만든다.

 

그럼 product 를 사용하여 1 -> 2 -> 3 을 사라지게 할 수 있는 경우의 수를 모두 구한다.

 

단, card[i] 의 길이가 4이상인 경우(i 의 캐릭터 카드가 4장 이상인 경우를 말한다.) card[i][j] 의 길이를 2개씩 분할해서 array 에 담는다. 3의 캐릭터 카드가 4장인 경우 1 -> 3 -> 2 -> 3 의 경우를 처리하기 위함이다.

 

구한, array 를 permutation 하여 1 -> 2 -> 3, 1 -> 3 -> 2, ..., 3 -> 2 -> 1 의 경우에 대해 준비를 한다.

 

여기서 case 라는 배열을 만들어 첫 원소를 (r, c) 로 두고 구한 각각의 경우에 대해서 순서대로 case 에 좌표를 담았다. (편의를 위해 2차원 배열을 1차원 배열로 만들었다.)

 

반복문을 사용하여 case[i] 에서 case[i+1] 로 가는 최단 거리를 bfs 알고리즘을 구현하여 각각의 경우에 대해서 거리를 구하고 그 중에서 최솟값을 반환하였다.

 

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

answer = float('inf')

def solution(board, r, c):
    global answer    
    card = defaultdict(list)
    
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                card[board[i][j]].append((i, j))
    
    for key in card.keys():
        card[key] = list(permutations(card[key]))
    
    for i in list(product(*list([card[i] for i in card.keys()]))):
        array = []
        
        for j in i:
            if len(j) > 2:
                for k in range(len(j) // 2):
                    array.append(j[2*k:2*(k+1)])
            else:
                array.append(j)
        
        for case_ in list(permutations(array)):
            temp = copy.deepcopy(board)
            d = 0
            case = [(r, c)]
            
            for e in case_:
                case.extend(e)
            
            for j in range(len(case)-1):
                if case[j] != case[j+1]:
                    d = bfs(case[j], case[j+1], temp, d)
                else: 
                    d += 1
                    
            answer = min(answer, d)
            
    return answer

def bfs(start, end, board, d):
    answer = 0
    queue = deque([start])
    directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    dic = defaultdict(int)
    dic[start] = d
    
    while queue:
        x, y = queue.popleft()
        
        for i, j in directions:
            x_, y_ = x + i, y + j
            
            if 0 <= x_ < 4 and 0 <= y_ < 4: 
                if dic[(x_, y_)] == 0 or dic[(x_, y_)] > dic[(x, y)] + 1:
                    dic[(x_, y_)] = dic[(x, y)] + 1
                    queue.append((x_, y_))
                
                while True:
                    if board[x_][y_] != 0 or (x_ in [0, 3] if i != 0 else y_ in [0, 3]):
                        if dic[(x_, y_)] == 0 or dic[(x_, y_)] > dic[(x, y)] + 1:
                            dic[(x_, y_)] = dic[(x, y)] + 1
                            queue.append((x_, y_))
                        
                        break
                    
                    x_ += i
                    y_ += j
                    
        if dic[end] != 0:
            answer = dic[end] + 1
            
            if board[start[0]][start[1]] == board[end[0]][end[1]]:
                board[start[0]][start[1]] = 0
                board[end[0]][end[1]] = 0
                   
            return answer

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