문제
- 문제 링크
- 문제 설명: 현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
- 유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집음. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료
- 커서 키 조작은 상하좌우로 1칸씩 이동가능하며, 상하좌우에서 가장 가까운 카드로 이동하거나 없으면 마지막 칸으로 이동하는 점프 조작도 있다.
- 1칸 이동, 점프 이동, 카드 뒤집기 모두 1회 조작한 것으로 본다.
- 입력
- board는 4 x 4 크기의 2차원 배열
- board 배열의 각 원소는 0 이상 6 이하인 자연수 (0은 빈칸)
- 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미
- 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않음
- r은 커서의 최초 세로(행) 위치, c는 커서의 최초 가로(열) 위치
- 게임 화면의 좌측 상단이 (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 |
풀이
- 서로 다른 카드를 뒤집게 되는 경우는 없다고 가정
- 카드 쌍의 각 좌표를 배열에 저장
- 카드의 종류가 최대 6가지이므로, 매 카드마다 제거하는 순서를 조합해서 최소 비용을 탐색
- 카드를 제거할 때 순서에 영향을 받으므로 "1번 카드 쌍 뒤집기 -> 2번 카드 쌍 뒤집기" 와 "2번 카드 쌍 뒤집기 -> 1번 카드 쌍 뒤집기" 의 경우는 다른 케이스로 생각해야 함
- 카드가 이미 제거되었는지는 정수형 변수에 1-bit를 저장해서 판단
- 제거되지 않은 카드 중에서 하나씩 제거하면서 비용을 계산하는데 두 카드 사이의 거리를 계산하는 함수(cost)를 DFS로 구현
- cost(pii& src, pii& dest, int visited) := src에서 dest로 이동할 때 최소 조작 횟수 반환
- visited는 현재 좌표의 방문 유무이며 4x4 배열이기 때문에 칸의 개수가 총 16개라 (1 << (y*4+x)) 번째 비트를 on/off 하여 파악할 수 있음
- 카드 뒤집기 연산은 포함하지 않고 이동만 포함
- dfs(pii cursor, int flipped, vector<pair<pii, pii>> loc) := 현재 커서의 위치 cursor와 현재 뒤집힌 카드 목록 flipped 와 각 카드의 좌표가 담긴 배열 loc 주어질 때 모두 뒤집을 때까지 필요한 최소 비용 반환
- 주의할 점: cost(src, dest, 0) 와 cost(dest, src, 0) 의 결과는 다를 수 있음
- 예를 들어, 아래와 같은 경우 라이언 카드는 위 함수의 호출 결과 각각 3과 2가 됨.
#include <string>
#include <vector>
#include <algorithm>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;
const int INF = 1e9;
const int d[5] = {0, -1, 0, 1, 0};
vector<vector<int>> B;
int cost(pii src, pii dest, int visited) {
if (src.Y == dest.Y and src.X == dest.X) return 0;
int ret = INF;
for (int i = 0; i < 4; i++) {
int ny = src.Y + d[i];
int nx = src.X + d[i+1];
if (ny < 0 or ny >= 4 or nx < 0 or nx >= 4 or (visited & (1 << (ny*4 + nx))))
continue;
// 1칸씩 이동
int nextVisited = visited | (1 << (src.Y*4 + src.X));
ret = min(ret, cost({ny, nx}, dest, nextVisited) + 1);
// 점프 이동
if (ny == src.Y) {
while (nx > 0 and nx < 3 and B[ny][nx] == 0) {
nextVisited |= (1 << (ny*4 + nx));
nx += d[i+1];
}
if (nx == src.X + d[i+1]) continue; // 1칸 이동한 것과 같으면 스킵
} else {
while (ny > 0 and ny < 3 and B[ny][nx] == 0) {
nextVisited |= (1 << (ny*4 + nx));
ny += d[i];
}
if (ny == src.Y + d[i]) continue; // 1칸 이동한 것과 같으면 스킵
}
ret = min(ret, cost({ny, nx}, dest, nextVisited) + 1);
}
return ret;
}
int dfs(pii cursor, int flipped, vector<pair<pii,pii>>& loc) {
int ret = INF;
for (int i = 0; i < 6; i++) {
// 이미 뒤집혀 제거되었거나 존재하지 않는 카드이면 continue
if ((flipped & (1 << i)) or loc[i].first.Y == -1) continue;
pii& src = loc[i].first;
pii& dest = loc[i].second;
// 현재 커서 위치에서 카드쌍의 각 위치까지 조작 비용을 계산해서 비교
int cost1 = cost(cursor, src, 0) + cost(src, dest, 0);
int cost2 = cost(cursor, dest, 0) + cost(dest, src, 0);
B[src.Y][src.X] = B[dest.Y][dest.X] = 0;
cost1 += dfs(dest, flipped | (1 << i), loc);
cost2 += dfs(src, flipped | (1 << i), loc);
ret = min(ret, min(cost1, cost2) + 2); // 2 = flipping cost
B[src.Y][src.X] = B[dest.Y][dest.X] = i+1;
}
return ret == INF ? 0 : ret;
}
int solution(vector<vector<int>> board, int r, int c) {
B = board;
vector<pair<pii,pii>> loc(6, {{-1, -1}, {-1, -1}});
for (int y = 0; y < 4; y++)
for (int x = 0; x < 4; x++)
if (board[y][x] > 0)
if (loc[board[y][x]-1].first.Y == -1)
loc[board[y][x]-1].first = {y, x};
else
loc[board[y][x]-1].second = {y, x};
return dfs({r, c}, 0, loc);
}