2021 카카오 코딩테스트 lv.3 카드 짝 맞추기 파이썬

from collections import deque


def ctrl_move(r, c, dr, dc, board):
    while True:
        r += dr
        c += dc
        if 0 <= r < 4 and 0 <= c < 4:
            if board[4 * r + c] != '0':
                return r, c
        else:
            return r - dr, c - dc


def solution(board, r, c):
    board = ''.join(str(a) for b in board for a in b) #문자열 변환
    q = deque([(r, c, -1, 0, board)])
    visited = set()
    dir = ((-1, 0), (0, 1), (1, 0), (0, -1))

    while q:
        r, c, enter, cnt, board = q.popleft() # enter = -1 -> 현재 뒤집은 카드 없음
        if board.count('0') == 16:
            return cnt
        if (r, c, enter, board) in visited:
            continue
        visited.add((r, c, enter, board))
        
        for dr, dc in dir:
            nr, nc = r + dr, c + dc
            if 0 <= nr < 4 and 0 <= nc < 4:
                q.append((nr, nc, enter, cnt + 1, board))
                cr, cc = ctrl_move(r, c, dr, dc, board)
                q.append((cr, cc, enter, cnt + 1, board))

        position = 4 * r + c

        if board[position] != '0':
            if enter == -1:
                q.append((r, c, position, cnt + 1, board))
            elif board[enter] == board[position] and enter != position:
                board = board.replace(board[enter], '0') # 카드 짝을 모두 0으로 바꿔줍니다
                q.append((r, c, -1, cnt + 1, board))

카드가 1,2 총 2짝이 있다면

모든 경우의 수는

1a->1b->2a->2b

1a->1b->2b->2a

1b->1a->2a->2b

1b->1a->2b->2a

총 4가지 입니다. 격자가 4*4로 작기때문에, bfs로 모든 경우를 확인합니다.

 

board를 문자열로 바꾸는 이유는 만약 리스트 형태에서 수정한다면 현재 q에 들어있는 모든 board도 같이 수정되기 때문에 매번 board를 copy 해줘야 하는 번거로움이 있기 때문입니다.

 

enter = -1 일땐, 현재 뒤집은 카드가 없습니다.

enter != -1 일땐, 현재 카드를 하나 뒤집은 상태이고, 카드의 위치를 나타냅니다.

 

만약 현재 위치와 enter가 다르면서 현재위치의 카드와 enter의 카드가 같다면, 둘다 뒤집어주고 0으로 바꿔줍니다.