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

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

풀이

2021 카카오 문제인, 카드 짝 맞추기 라는 문제이다.

처음 봤을 땐, 어떻게 풀어야 할 지 감이 오지 않았다.
그러다 조건이 4x4 배열임을 확인하고.. "아 전부 다 테스트 해보라는거구나.."
특정 위치에서 경우의 수는 9가지이다.

• 4방향 이동
• 4방향 Ctrl 이동
• Enter

말 그대로 모두 다 구현했다.
그리고 배열을 문자열로 수정해서 풀었다.
그 이유는 파이썬에서 배열은 mutable한 object 이므로 계속 deep copy해주기가 귀찮았다.

솔직히 내 코드가 마음에 들지는 않는데, 새로운 문제라 다른 분들이 포스팅한 좋은 코드를 발견하지는 못했다.
카카오 문제에서 구현이 조금 하드한 문제가 많이 나오는구나 깨달았던 문제였다.

from collections import deque
import copy

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

def end_game(b):
    if b.count("0") == 16:
        return True
    return False

def remove_element(b, e):
    b = b.replace(e, "0")
    return b

def move(b, y, x, dy, dx):
    ny, nx = y + dy, x + dx
    if ny >= 0 and ny < 4 and nx >= 0 and nx < 4 and b[ny * 4 + nx] == "0":
        return move(b, ny, nx, dy, dx)
    else:
        if ny >= 0 and ny < 4 and nx >= 0 and nx < 4:
            return (ny, nx)
        else:
            return (y, x)

def solution(board, r, c):
    answer = 0
    b = ""
    for i in range(4):
        for j in range(4):
            b += str(board[i][j])
    q = deque([])

    cnt = 0
    enter = -1 # enter을 클릭했던 위치
    q.append((r, c, b, cnt, enter))
    s = set()

    while q:
        y, x, b, c, e = q.popleft()
        pos = 4 * y + x

        if (y, x, b, e) in s:
            continue
        s.add((y, x, b, e))

        if end_game(b):
            return c

        # 4 방향 이동
        for (dy, dx) in d:
            ny, nx = y + dy, x + dx
            if ny >= 0 and ny < 4 and nx >= 0 and nx < 4:
                q.append((ny, nx, b, c+1, e))

        # Ctrl + 4 방향 이동
        for (dy, dx) in d:
            ny, nx = move(b, y, x, dy, dx)
            if ny == y and nx == x:
                continue
            q.append((ny, nx, b, c+1, e))

        # enter를 하는 경우
        if b[pos] != 0:
            if e == -1:
                n_e = pos
                q.append((y, x, b, c+1, n_e))
            else:
                if e != pos and b[e] == b[pos]:
                    b = remove_element(b, b[e])
                    q.append((y, x, b, c+1, -1))

    return answer