[프로그래머스] 코딩테스트 연습 - 카드 짝 맞추기 (Python)

코딩테스트 연습 - 카드 짝 맞추기 [2021 KAKAO BLIND RECRUITMENT]

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

처음 생각보다 쉽지 않은 문제였던 것 같습니다. 물론 제가 생각이 짧아 헤맨 시간이 대부분이지만ㅎㅎ..

역시 문제를 빠르게 읽고 풀이를 시작하는 것보다 문제를 꼼꼼히 읽고 한 번에 푸는 것이 더욱 좋다는 것을 다시 한번 느끼네요..

 

풀이

먼저 간단하게 제가 풀이한 방법을 적어보자면 아래와 같습니다.

1. Permutation을 사용하여 선택할 카드의 순서를 정합니다.

2. 모든 경우의 순서에 대해 조작 횟수가 가장 적은 것을 반환합니다.

 

위의 방식을 자세하게 적어보겠습니다.

1. Permutation을 사용하여 선택할 카드의 순서를 정합니다.

어떤 카드를 먼저 선택해야 조작 횟수가 최소가 될지는 탐색해보기 전에는 알 수가 없습니다. 그래서 저는 카드를 선택하는 모든 경우의 수를 구하고 완전 탐색을 진행했습니다. 완전 탐색을 해도 크게 부담이 되지 않는 이유는 먼저 board의 크기가 4x4이고 카드의 종류도 많지 않기 때문입니다.

 

2. 모든 경우의 순서에 대해 조작 횟수가 가장 적은 것을 반환합니다.

카드를 선택하는 과정을 식으로 나타낸다면 아래와 같은 조작 횟수를 가지게 됩니다.

현재위치에서 카드에 도달하기 위한 조작 횟수 + 도달한 카드에서 다음 카드까지의 조작 횟수

\( \bullet \) 여기서 신경 써야 할 부분은 어떠한 한 쌍의 카드 중에서 어떠한 카드를 먼저 선택해야 할지를 고려해야 합니다.

왜냐하면 조작 횟수는 한 쌍의 카드에서 어떤 카드를 먼저 선택하느냐에 따라 현재 위치에서의 조작 횟수와 선택한 카드에서 쌍이 되는 카드까지의 조작 횟수가 달라지기 때문입니다. (저는 여기서 A1 \( \rightarrow \) A2 조작 횟수가 A2 \( \rightarrow \) A1와 같을 것이라고 생각해서 좀 헤맸습니다ㅎㅎ)

 

\( \bullet \) 모든 경우를 파악했다면 조작 횟수를 구해야겠죠.

가능한 이동 조작의 경우는 "4가지 방향키"와 "4가지 ctrl+방향키"이므로  BFS를 통해 최단경로를 구하면 됩니다.

 

그렇다면 마지막으로 정해진 순서에 따라 조작 횟수를 구하는 순서는 다음과 같습니다.

1) 현재 위치에서 A1까지의 조작 횟수 + A1 \( \rightarrow \) A2까지의 조작 횟수 + 2(카드 선택)

2) 현재 위치에서 A2까지의 조작 횟수 + A2 \( \rightarrow \) A1까지의 조작 횟수 + 2(카드 선택)

마지막으로 1)과 2) 중에 더 적은 조작 횟수가 드는 것을 선택하고 이 과정을 주어진 순서에 따라 반복하면 되는 것이죠.

 

Code

from collections import defaultdict, deque
from itertools import permutations
from copy import deepcopy
def move_cost(board, start, end):   # 조작 횟수 Count
    if start==end: return 0
    queue, visit = deque([[start[0], start[1], 0]]), {start}
    while queue:                    # BFS
        x, y, c = queue.popleft()
        for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nx, ny = x+dx, y+dy     # Normal move
            cx, cy = x, y
            while True:             # Ctrl + move
                cx, cy = cx+dx, cy+dy
                if not (0 <= cx <= 3 and 0 <= cy <= 3):
                    cx, cy = cx-dx, cy-dy
                    break
                elif board[cx][cy] != 0:
                    break

            if (nx, ny) == end or (cx, cy) == end:  # 도착 최단 경로
                return c+1

            if (0 <= nx <= 3 and 0 <= ny <= 3) and (nx, ny) not in visit:
                queue.append((nx, ny, c+1))
                visit.add((nx, ny))
            if (cx, cy) not in visit:
                queue.append((cx, cy, c+1))
                visit.add((cx, cy))

def cls_cost(board, cdict, curr, order, cost):
    if len(order)==0: return cost   # 모든 카드를 확인한 경우
    idx = order[0]+1                # 현재 선택해야할 카드의 종류

    # 현재위치에서 A1까지의 조작 횟수 + A1->A2까지의 조작 횟수 + 2(카드 선택)
    choice1 = move_cost(board, curr, cdict[idx][0]) + move_cost(board, cdict[idx][0], cdict[idx][1]) + 2
    choice2 = move_cost(board, curr, cdict[idx][1]) + move_cost(board, cdict[idx][1], cdict[idx][0]) + 2

    # 선택한 카드는 board에서 0으로 변경
    new_board = deepcopy(board)
    new_board[cdict[idx][0][0]][cdict[idx][0][1]] = 0
    new_board[cdict[idx][1][0]][cdict[idx][1][1]] = 0

    if choice1 < choice2:   # 적은 조작 횟수를 한 경우를 따라 재귀
        return cls_cost(new_board, cdict, cdict[idx][1], order[1:], cost + choice1)
    else:
        return cls_cost(new_board, cdict, cdict[idx][0], order[1:], cost + choice2)

def solution(board, r, c):
    answer = float('inf')
    cdict = defaultdict(list)
    for row in range(4):        # 카드의 종류에 따라 좌표 저장
        for col in range(4):
            num = board[row][col]
            if num != 0:
                cdict[num].append((row, col))

    for case in permutations(range(len(cdict)), len(cdict)):    # 완전 탐색
        answer = min(answer, cls_cost(board, cdict, (r, c), case, 0))

    return answer

 

 

문제 설명

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

게임에서 카드를 선택하는 방법은 다음과 같습니다.

• 카드는 커서를 이용해서 선택할 수 있습니다.
  • 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
• 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
  • [Enter] 키를 입력해서 카드를 뒤집었을 때
    • 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
    • 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.
아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.

예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.

[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회

[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회

[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회

위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.

 

 

문제

현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

 

 

제한사항

• board는 4 x 4 크기의 2차원 배열입니다.
• board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
  • 0은 카드가 제거된 빈 칸을 나타냅니다.
  • 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
  • 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
• r은 커서의 최초 세로(행) 위치를 의미합니다.
• c는 커서의 최초 가로(열) 위치를 의미합니다.
• r과 c는 0 이상 3 이하인 정수입니다.
• 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.

 

 

입출력 예

board	r	c	result
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]	1	0	14
[[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]	0	1	16

 

입출력 예 #1
문제의 예시와 같습니다.

 

입출력 예 #2
입력으로 주어진 게임 화면은 아래 그림과 같습니다.

위 게임 화면에서 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값은 16번 입니다.