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

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

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

dir = [(0,1),(0,-1),(1,0),(-1,0)]

def make_nums(board):
    nums = defaultdict(list)
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                nums[board[i][j]].append((i, j))
    return nums

def get_cost(r1, c1, r2, c2, board):
    q = deque([(0, r1, c1)])

    while q:
        cost, r, c = q.popleft()
        if r == r2 and c == c2:
            return cost + 1
        for d in dir:
            nw_r = r+d[0]
            nw_c = c+d[1]
            if 0 <= nw_r < 4 and 0 <= nw_c < 4:
                q.append((cost+1, nw_r, nw_c))
        for d in dir:
            nw_r = r+d[0]
            nw_c = c+d[1]
            while 0 <= nw_r < 4 and 0 <= nw_c < 4 and board[nw_r][nw_c] == 0:
                nw_r += d[0]
                nw_c += d[1]
            if not(0 <= nw_r < 4 and 0 <= nw_c < 4):
                nw_r -= d[0]
                nw_c -= d[1]
            q.append((cost+1, nw_r, nw_c))
    return -1

def get_all_cost(order, nums, board, r, c, memo):
    if not order:
        return 0

    card = order[0]
    first_r, first_c = nums[card][0][0], nums[card][0][1]
    second_r, second_c = nums[card][1][0], nums[card][1][1]

    key = tuple(map(tuple, board)) + (r, c, card, 1)
    if memo[key] != 0:
        to_first_cost = memo[key]
        board[first_r][first_c] = 0
        board[second_r][second_c] = 0
    else:
        to_first_cost = get_cost(r, c, first_r, first_c, board)
        board[first_r][first_c] = 0
        to_first_cost += get_cost(first_r, first_c, second_r, second_c,board)
        board[second_r][second_c] = 0
        memo[key] = to_first_cost

    to_first_cost += get_all_cost(order[1:], nums, board, second_r, second_c, memo)
    board[first_r][first_c] = card
    board[second_r][second_c] = card

    key = key[:-1] + (r, c, card, 2)
    if memo[key] != 0:
        to_second_cost = memo[key]
        board[second_r][second_c] = 0
        board[first_r][first_c] = 0
    else:
        to_second_cost = get_cost(r, c, second_r, second_c, board)
        board[second_r][second_c] = 0
        to_second_cost += get_cost(second_r, second_c, first_r, first_c, board)
        board[first_r][first_c] = 0
        memo[key] = to_second_cost

    to_second_cost += get_all_cost(order[1:], nums, board, first_r, first_c, memo)
    board[first_r][first_c] = card
    board[second_r][second_c] = card

    return min(to_first_cost, to_second_cost)

def solution(board, r, c):
    answer = sys.maxsize
    nums = make_nums(board)
    num_order = list(permutations(nums, len(nums)))
    memo = defaultdict(int)

    for order in num_order:
        answer = min(answer, get_all_cost(order, nums, board, r, c, memo))

    return answer

• 모든 케이스를 확인해야함
  
  • 카드를 선택하는 순서에 따라 결과가 달라짐
  • 같은 숫자의 카드도 두 카드 중 어느 카드부터 선택하는지에 따라 결과가 달라짐
• 고려해야할 것
  • 위치를 이동할 때
    - 4방향
    - ctrl+방향시 카드를 만나면 카드에서 멈추고, 아니면 끝까지 이동
  • DP 사용시 key
    - 나는 board + 현재 위치(r, c) + 카드 번호 + 첫 번째/두 번째 카드를 사용
    - key 선택에 따라서 시간초과 발생
    - 첫 번째/두 번째 카드를 반드시 고려해야함!

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 문제에서 데이터의 범위가 작은 경우는 구현이 복잡한 문제인 듯 하다
  
  • grid도 4x4로 고정이고, 카드 종류도 1~6이라 간단해보인다
  • 그러나 고려해야할 사항이 많다
  • 그만큼 계산량이 많기 때문에, 더더욱 복잡하다