2021 KAKAO BLIND RECRUITMENT: 카드 짝 맞추기

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

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

 

파이썬

from collections import deque


def solution(board, r, c):
    answer = 0
    board = ''.join(str(each) for row in board for each in row)
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque([(r, c, 0, -1, board)])  # bfs, y, x, count, enter, board
    visited = set()
    while que:
        y, x, count, enter, board = que.popleft()
        if board.count('0') == 16:  # end
            return count
        if (y, x, enter, board) in visited:
            continue
        visited.add((y, x, enter, board))

        for dy, dx in directions:  
            ny, nx = y + dy, x + dx  # move
            if 0 <= ny < 4 and 0 <= nx < 4:
                que.append((ny, nx, count + 1, enter, board))
            ny, nx = ctrl_move(y, x, dy, dx, board)  # ctrl + move
            if ny == y and nx == x:
                continue
            que.append((ny, nx, count + 1, enter, board))
        position = y * 4 + x  # enter
        
        if board[position] != 0:
            if enter == -1:
                que.append((y, x, count + 1, position, board))
            elif enter != position and board[enter] == board[position]:
                board = board.replace(board[enter], '0')
                que.append((y, x, count + 1, -1, board))
    return answer


def ctrl_move(y, x, dy, dx, board):
    ny, nx = y + dy, x + dx
    if 0 <= ny < 4 and 0 <= nx < 4:
        if board[ny * 4 + nx] == '0':
            return ctrl_move(ny, nx, dy, dx, board)
        else:
            return ny, nx
    else:
        return y, x

테스트 1 〉	통과 (9.67ms, 10.6MB)
테스트 2 〉	통과 (7.10ms, 10.4MB)
테스트 3 〉	통과 (10.77ms, 10.5MB)
테스트 4 〉	통과 (10.04ms, 10.5MB)
테스트 5 〉	통과 (17.54ms, 10.7MB)
테스트 6 〉	통과 (17.42ms, 10.8MB)
테스트 7 〉	통과 (18.12ms, 10.8MB)
테스트 8 〉	통과 (18.47ms, 10.7MB)
테스트 9 〉	통과 (39.86ms, 11.5MB)
테스트 10 〉	통과 (54.67ms, 11.6MB)
테스트 11 〉	통과 (37.23ms, 11.5MB)
테스트 12 〉	통과 (41.39ms, 11.6MB)
테스트 13 〉	통과 (97.19ms, 12.5MB)
테스트 14 〉	통과 (81.30ms, 12.3MB)
테스트 15 〉	통과 (84.55ms, 12.4MB)
테스트 16 〉	통과 (95.53ms, 12.4MB)
테스트 17 〉	통과 (1.01ms, 10.3MB)
테스트 18 〉	통과 (0.66ms, 10.4MB)
테스트 19 〉	통과 (3.55ms, 10.3MB)
테스트 20 〉	통과 (2.24ms, 10.4MB)
테스트 21 〉	통과 (17.72ms, 10.8MB)
테스트 22 〉	통과 (83.79ms, 12.3MB)
테스트 23 〉	통과 (89.61ms, 12.6MB)
테스트 24 〉	통과 (19.50ms, 10.8MB)
테스트 25 〉	통과 (81.64ms, 12.2MB)
테스트 26 〉	통과 (18.54ms, 10.8MB)
테스트 27 〉	통과 (18.83ms, 10.7MB)
테스트 28 〉	통과 (8.94ms, 10.4MB)
테스트 29 〉	통과 (7.93ms, 10.5MB)
테스트 30 〉	통과 (8.22ms, 10.6MB)