카드 짝 맞추기
programmers.co.kr/learn/courses/30/lessons/72415
코딩테스트 연습 - 카드 짝 맞추기
[[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
programmers.co.kr
1. 문제 설명
게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.
게임에서 카드를 선택하는 방법은 다음과 같습니다.
- 카드는 커서를 이용해서 선택할 수 있습니다.
- 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
- 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
- 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
- [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
- 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
- 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
- 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
- [Enter] 키를 입력해서 카드를 뒤집었을 때
- 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
- 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.
- [Enter] 키를 입력해서 카드를 뒤집었을 때
"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.
다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.
아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.
2. 문제
현재 카드가 놓인 상태를 나타내는 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) 입니다.
4. 해설
일단 먼저 여기 작성한 답은 6개의 Test case에 대해서 시간초과가 난 풀이다. 나중에 시간초과를 줄일 방법이 생각나면 고치거나 아님 여러분들의 의견을 기다리겠다.
아이디어는 다음과 같다. 크게 2가지 알고리즘 다익스트라와 브루트포스 섞여있는문제로 보면 된다. 먼저 카드 방문 순서를 브루트포스로 탐색해야하고 해당 경로의 최단거리를 다익스트라를 이용해 구해서 더해주면 된다.
문제에서 주어진 최대 카드 수가 작기 때문에 모든 경우의 수를 고려하는 브루트포스를 사용하면 된다. 전체 카드 종류가 최대 6개이고 각 카드 종류마다 2개의 카드가 존재하므로 최대 경우의 수가 6! * 64 = 7680개
게임보드에 카드 1,2,3 이 있다고 가정해보면 카드 방문 순서에 따라 전체 경로의 최소 동작 횟수가 달라질 것이다. (ABC ,CBA, BCA, ....) 이런식으로 N개의 카드에서 N개를 순서에 관련있게 뽑는 경우의 수(순열, nPn)를 구하면 된다.
이걸로 끝이냐? 아니다.
카드는 쌍으로 구성된다. 같은 그림의 카드가 2장씩 있기 때문에 각각의 카드를 Card1, Card2라고 할 때 각각의 카드 쌍마다 방문할 수 있는 방법이 2가지이다. (Card1 -> Card2 또는 Card2 -> Card1) 따라서 위에서 구한 경우의 수에 2^n을 해주면 된다.
정리해보면 전체 경우의 수는 아래와 같다.
(n개의 카드에서 n개를 순서에 상관있게 뽑는 경우의 수 ) * (카드 짝 순서를 바꾸는 경우의 수)
이제 구현을 해보면 아래와 같다.
import heapq as hq
import copy
from collections import deque
moves =[[1,0],[-1,0],[0,-1],[0,1]]
#방향키로만 움직일 때
def withoutCtrl(board,row,col):
result =[]
for drow, dcol in moves:
nrow = row + drow
ncol =col +dcol
if 0<= nrow < 4 and 0<= ncol < 4:
result.append((nrow, ncol,))
return result
#컨트롤을 이용해 움직일 때
def withCtrl(board,r, c):
result =[]
for drow, dcol in moves:
row=r
col=c
while True:
row += drow
col += dcol
if row < 0 or row >= 4 or col < 0 or col >= 4:
if not(row-drow == r and col-dcol == c):
result.append([row-drow, col-dcol])
break
if board[row][col] != 0:
result.append([row, col])
break
return result
#start에서 target까지 가는 최단 거리를 찾는 알고리즘
#다익스트라
def bfs(board ,start, target):
discovered = [[[0,0] for j in range(4)] for i in range(4)]
queue = []
r, c = start
#시작점이 카드 일 수도 있고 아닐 수도 있음
if board[r][c] != 0: # 카드라면
board[r][c] = 0
hq.heappush(queue, (1, r, c,),) #Enter를 한번 치고 시작
else: # 빈공간이라면
hq.heappush(queue, (0, r, c,),) #Enter를 안치고 시작
while queue:
cnt, row, col = hq.heappop(queue)
#타겟 위치에 도달하면
if target == (row,col,):
board[row][col] = 0
#엔터를 쳐주고 반환
cnt+=1
return cnt
#방향키로만 움직일 때
for nrow, ncol in withoutCtrl(board, row, col):
if not discovered[nrow][ncol][0]:
discovered[nrow][ncol][0] = 1
hq.heappush(queue,(cnt+1, nrow, ncol,))
#컨트롤키를 사용할 떄
for nrow, ncol in withCtrl(board, row, col):
if not discovered[nrow][ncol][1]:
discovered[nrow][ncol][1] = 1
hq.heappush(queue,(cnt+1, nrow, ncol,))
return
def solution(board, r, c):
answer = float('inf')
target_list ={}
#카드의 위치와 카드 번호를 저장해둔다.
for i in range(4):
for j in range(4):
num = board[i][j]
if num == 0:
continue
if not target_list.get(num, None):
target_list[num] = [(i,j,)]
else:
target_list[num].append((i,j,))
#카드위치를 저장한 리스트
card_list = list(target_list.values())
#n개에서 n개를 뽑는 경우의 수 * 카드 뒤집기 경우의 수
#여기서 시간초과가 나는 것 같다.
used =[0 for i in range(len(card_list))]
cases=deque()
def permutation(arr, r):
if len(arr) == r:
case = [i for i in arr]
cases.append(case)
return
for i in range(len(card_list)):
if not used[i]:
for o in range(2):
arr.append([card_list[i][o],card_list[i][o-1]])
used[i] = 1
permutation(arr, r)
used[i] = 0
arr.pop()
permutation([], len(card_list))
#cases안에 우리가 찾는 모든 경우의 수가 들어 있다.
for case in cases:
# 보드 초기화
now_loc = (r,c,)
cnt = 0
#카드 쌍에 대해서 아래처럼 진행
for card1, card2 in case:
# 현재 위치와 카드1의 위차 같다면 한번만 진행 card1 -> card2
if card1==now_loc:
cnt += bfs(board, card1, card2)
#아니라면 now_loc -> card1 -> card2
else:
cnt += bfs(board, now_loc, card1)
cnt += bfs(board, card1, card2)
now_loc = card2
#최소값을 저장한다.
answer = min(answer, cnt)
#보드 초기화
for card_num, locs in target_list.items():
for row, col in locs:
board[row][col] = card_num
return answer'Algorithm > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 트리 트리오 python (0) | 2021.06.06 |
|---|---|
| [programmers] 다단계 칫솔 판매 python (0) | 2021.05.29 |
| [프로그래머스] 자물쇠와 열쇠 python (0) | 2021.04.26 |
| [프로그래머스] 후보키 python (0) | 2021.04.22 |
| [프로그래머스] N으로 표현 python (0) | 2021.04.22 |