[프로그래머스] 카드 짝 맞추기 파이썬 풀이

카드 짝 맞추기 (Lv.3)

구현이 복잡한 문제다. 각 함수를 잘 설계하고 테스트 후 조합해서 풀 수 있어야 한다.

문제 요구사항

• 문제에서 말하는 게임은 보통 알고있는 그 카드 짝 맞추기 게임 형식이다.
• 현재 커서가 정해져 있고, 방향키 혹은 ctrl + 방향키로 조작이 가능하다.
• 방향키는 상하좌우, ctrl + 방향키는 각 방향의 가장 가까운 카드나 벽 으로 이동한다.
• 카드가 있는 위치에서 Enter 키로 카드를 뒤집을 수 있다.
• 같은 카드 짝을 뒤집으면 카드가 사라진다.
• 이 때 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 반환하라.

문제 접근

• 게임 판이 4x4로 정해져 있어서 필요성 연산이 적으므로 효율성 문제는 고려하지 않아도 된다.
• => 완전 탐색을 이용해 보자.
• 문제를 단계 별로 나누어 보았다.

1. 뒤집을 카드 선택, 이동, 뒤집기
2. 같은 번호 카드 선택, 이동, 뒤집기
3. 게임판이 모두 0이 될 때까지 1~2번 반복

• 이제 이동거리를 구하는 함수를 구현하면 된다.
  • Ctrl + 방향키, 방향키 이동 좌표를 구하고 bfs queue에 저장하며 탐색하면 된다.

코드

from copy import deepcopy
from math import inf
from collections import deque

def get_key_count(board, cy, cx, ty, tx):
    dy = [1, 0, 0, -1]
    dx = [0, 1, -1, 0]
    que = deque()
    que.append((cy, cx))
    visited = [[inf for _ in range(4)] for _ in range(4)]
    visited[cy][cx] = 0
    while que:
        y, x = que.popleft()
        if y == ty and x == tx:
            return visited[y][x]
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < 4 and 0 <= nx < 4 and visited[ny][nx] > visited[y][x] + 1:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny, nx))

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            while 0 <= ny + dy[i] < 4 and 0 <= nx + dx[i] < 4 and board[ny][nx] == 0:
                ny, nx = ny + dy[i], nx + dx[i]
            if 0 <= ny < 4 and 0 <= nx < 4 and visited[ny][nx] > visited[y][x] + 1:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny, nx))


# # test
# board = [[1,0,0,3],[0,0,0,0],[0,0,0,2],[3,0,1,0]]
# print(get_key_count(board, 0, 3, 0 ,3))

def get_coord_by_num(board, target):
    for i in range(4):
        for j in range(4):
            if board[i][j] == target:
                return i, j

answer = inf

def is_end(board):
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                return False
    return True


def dfs(board, r, c, ty1, tx1, cnt):
    global answer
    board = deepcopy(board)
    target_num = board[ty1][tx1]

    # 첫 번째 카드
    cnt += get_key_count(board, r, c, ty1, tx1)
    board[ty1][tx1] = 0
    # 두 번째 카드
    ty2, tx2 = get_coord_by_num(board, target_num)
    cnt += get_key_count(board, ty1, tx1, ty2, tx2)
    board[ty2][tx2] = 0
    cnt += 2
    if is_end(board):
        answer = min(answer, cnt)
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                dfs(board, ty2, tx2, i, j, cnt)

def solution(board, r, c):
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                dfs(board, r, c, i, j, 0)

    return answer

풀고 나서

• 80분 + a 소요

• while, if문 구현하는데 헷갈려서 디버깅을 좀 했다. 무지성 디버깅하지 말고 생각을 더 해보자

• 이렇게 작동해서 bfs할 때 못 썼다. 어떻게 사용해야 할지 알아봐야겠다.

• 함수 단위테스트 해본 것이 좀 도움이 됐다.