문제
https://school.programmers.co.kr/learn/courses/30/lessons/72415
입력
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c
출력
모든 카드를 제거하기 위한 키 조작 횟수의 최솟값
풀이
제한조건
- board는 4 x 4 크기의 2차원 배열입니다.
- board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
- 0은 카드가 제거된 빈 칸을 나타냅니다.
- 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
- 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
- r은 커서의 최초 세로(행) 위치를 의미합니다.
- c는 커서의 최초 가로(열) 위치를 의미합니다.
- r과 c는 0 이상 3 이하인 정수입니다.
- 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.
접근방법
잘못된 접근으로 풀이에 시간이 오래걸렸다.
일단 문제는 단순 탐색문제이다.
BFS를 통해 단순 접근하는 방법을 생각해봤다.
접근1.
1. 현재 커서의 위치에서 가장 가까운 카드를 찾는다.
a. 가장 가까운 카드로 이동하며 키 조작 횟수 계산.
2. BFS를 수행하며 해당 카드와 짝을 이루는 카드를 찾는다.
b. 해당 카드를 찾는 과정에서 발생하는 키 조작 횟수 계산.
3. 짝을 찾았다면 엔터 입력 2번을 계산하고, 1번 과정으로 돌아간다.처음 위와 같이 구현했으나, 오류가 있었다.
과연 가장 가까운(현재 위치에서 최소의 조작으로 도달할 수 있는 카드)부터 처리하는게 맞는가? 라는 의문이 들어 반례를 생각해보았다.
아래와 같은 예시라면, 2를 먼저 처리하는게 최소 조작이지만, 가장 가까운 1부터 처리하면 1번 더 많은 조작이 필요하다.
커서의 위치 : 0,0
1221
0000
0000
0000반례를 생각해보니 접근 방법 자체가 잘못되었음을 알게되었다.
접근2
순열, DFS와 같이 순서를 정해서 탐색해보고 비용을 계산하는 방법이다.
현재 커서의 위치와 상관없이 모든 경우의 수를 따져보는것이다.
1->2->3 순으로 카드를 제거하는 경우와 2->1->3으로 처리하는 것은 비용이 다르다.
또한 같은 1->2->3순으로 처리하더라도, 현재 커서의 위치와 해당 번호를 가진 2개의 카드의 위치에 따라 비용이 달라질 수 있다고 생각했다.
따라서 아래와 같이 접근하였다.
1. 어떤 순서로 카드를 방문할지 순서를 정한다.
2. 순서를 정했다면, 특정 번호의 카드를 제거하기 위한 경우의 수를 계산한다.
a. 특정 번호의 카드는 총 2개, 2가지를 모두 계산해본다.
3. 2번의 계산이 끝났다면, 해당 위치에서 다음 순서의 번호, 즉 2번 과정을 수행한다.예시와 함께 조금 더 자세히 보자면,
1->2->3의 순서로 방문한다고 생각해보자.
1번 카드를 제거하기로 했으므로, 커서를 1번위치로 옮겨야 한다.
이때, 1은 총 2개이므로, (0,0) 과 (3,2) 2가지가 존재하는데 2가지를 모두 수행한다.
- 커서의 현 위치 -> (0,0) -> (3,2) 이동
- 커서의 현 위치 -> (3,2) -> (0,0) 이동
이제 2개의 결과위치에서 다시 2를 제거하기 위한 동작을 시작한다.
2 또한 2개가 있으므로 2개의 경우로 나누고, 3을 제거한다.
모든 카드를 제거하였다면 비용을 계산해보고 최소 비용을 갱신한다.
그다음은 다음 순열인 1->3->2 순으로 반복한다.
예제 입력
커서의 위치 : (1,0)
1003
2000
0002
3010너무 단순하게 생긴 문제라고 단순하게 생각하지 말고,
충분히 생각해보고 접근하자..!
코드
import java.util.*;
class Point {
int x;
int y;
Point(int a, int b) {
x = a;
y = b;
}
}
class Solution {
int[][] map;
final int SIZE = 4;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int answer;
int R, C;
Point[][] points;
boolean[] selected;
boolean[] exists;
int numCard;
public int solution(int[][] board, int r, int c) {
// init
answer = Integer.MAX_VALUE;
R = r;
C = c;
map = board;
points = new Point[6 + 1][2];
exists = new boolean[6 + 1];
selected = new boolean[6 + 1];
setCardInfomation();
search(0, 0, new Point(r, c));
return answer;
}
private void search(int value, int depth, Point current) {
if (depth == numCard) {
answer = Math.min(answer, value);
return;
}
for (int i = 1; i <= numCard; ++i) {
// 해당 숫자가 존재하며, 고른적은 없어야 함.
if (!selected[i] && exists[i]) {
selected[i] = true;
// 같은 숫자를 방문하더라도, 순서에 따라 값이 달라질 수 있음.
// 각각을 방문했을때를 나누어 다음 depth로 가본다.
for (int j = 0; j < 2; ++j) {
Point first = points[i][j];
Point second = points[i][(j + 1) % 2];
int cost = getMoveCount(current, first) + getMoveCount(first, second) + 2;
// 뒤집어서 없어지면, 맵에서 사라진것과 같다.
map[first.x][first.y] = 0;
map[second.x][second.y] = 0;
// 다음 숫자 탐색
search(value + cost, depth + 1, second);
// 해당 탐색이 종료되었다. 복구.
map[first.x][first.y] = i;
map[second.x][second.y] = i;
}
selected[i] = false;
}
}
}
private int getMoveCount(Point start, Point end) {
Queue<Point> q = new ArrayDeque();
int[][] visit = new int[SIZE][SIZE];
q.add(start);
visit[start.x][start.y] = 1;
while (!q.isEmpty()) {
Point cur = q.poll();
if (cur.x == end.x && cur.y == end.y)
return visit[cur.x][cur.y] - 1;
// 단순 이동 체크
for (int d = 0; d < SIZE; ++d) {
int nextX = cur.x + dx[d];
int nextY = cur.y + dy[d];
if (isInRange(nextX, nextY) && visit[nextX][nextY] == 0) {
visit[nextX][nextY] = visit[cur.x][cur.y] + 1;
q.add(new Point(nextX, nextY));
}
}
// Ctrl 이동 체크
for (int d = 0; d < 4; ++d) {
int nextX = cur.x;
int nextY = cur.y;
while (isInRange(nextX, nextY)) {
nextX = nextX + dx[d];
nextY = nextY + dy[d];
if (!isInRange(nextX, nextY)) {
nextX = nextX - dx[d];
nextY = nextY - dy[d];
break;
}
if (map[nextX][nextY] != 0)
break;
}
if (visit[nextX][nextY] == 0) {
visit[nextX][nextY] = visit[cur.x][cur.y] + 1;
q.add(new Point(nextX, nextY));
}
}
}
return visit[end.x][end.y] - 1;
}
public void setCardInfomation() {
// 1부터 6까지의 카드가 있을 수 있음.
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
int value = map[i][j];
if (value != 0) {
if (!exists[value]) {
exists[value] = true;
numCard++;
points[value][0] = new Point(i, j);
} else {
points[value][1] = new Point(i, j);
}
}
}
}
}
public boolean isInRange(int x, int y) {
if (0 <= x && x < SIZE && 0 <= y && y < SIZE)
return true;
return false;
}
}
