문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/72415
풀이 과정
이 문제는 세부적으로는 최적의 이동경로를 구하는 문제이지만, 큰 틀에서는, 카드를 고르는 최적의 순서를 구하면 된다. 최적의 순서로 카드를 고르면서, 각 카드로 이동할 때 최적의 경로로 이동하면 된다.
1. 최적의 카드 고르기
먼저 카드의 위치를 모두 기록한다. 그 다음에 DFS를 이용해서 카드를 고르는 순열을 탐색했다.
예를 들어, 카드가 1, 2, 3, 4 이렇게 4쌍이 있으면 먼저 1번 카드 한쌍중 하나로 이동한 후, 다른 하나로 이동한다. 그다음에 2, 3, 4 카드쌍을 탐색하고 돌아온다. 1번에서 출발한 후 탐색이 끝나면, 처음으로 돌아와서 2번 카드쌍의 카드중 하나로 이동한다. 이런식으로 탐색을 반복한다.
탐색을 하면서 2. 최적의 경로 이동을 이용해서 최소 이동 횟수를 구한 후, 카드를 고르는 다른 경우의 수와 비교해서 가장 작은 값을 반환하면 된다.
카드로 이동한 후, 카드를 뒤집기 위해 enter를 입력하는 것도 키 조작횟수에 포함되므로, 카드를 한쌍을 고를 때마다 이동 횟수에 2를 더하면(카드 한쌍을 뒤집기 위해 필요한 조작 횟수) 최종 답안이 된다.
카드쌍의 카드를 고를 때, 각 카드를 고르는 경우의 수를 모두 고려해야 모든 경우의 탐색이 가능한데, 처음에는 이를 인지하지 못해서 테스트를 통과하지 못했다가 나중에 수정했었다.
2. 최적의 경로 이동
한 점으로부터 다른점까지 이동하는데 필요한 최소 이동 횟수는 기본적으로 BFS를 이용해 구할 수 있다.
최소 이동 횟수를 구하는 다른 문제들과 이 문제의 차이점은, 이 문제의 경우 이동할 수 있는 방법이 최대 8가지라는 것이었다.
상하좌우 한칸 이동하는 경우의 수, 상하좌우 가장 가까운 카드(또는 맨 끝)로 이동하는 경우의 수를 모두 탐색했다.
최종 코드
move()메서드는 한 점으로 부터 다른 점까지 이동하는 최소 이동횟수를 구하는 메서드이다. queue의 요소로 들어가는 int 배열에는 {x좌표, y좌표, 해당 좌표까지 이동 횟수}를 저장했다.
카드 한쌍을 Card 객체로 만들어서 관리했다. 이 객체에는 각 카드의 위치와 카드 번호가 저장되고, 카드가 뒤집혔는지 여부도 저장한다(deleted).
카드 한쌍에는 두 카드가 있으므로, 현 위치에서 카드1로 이동 -> 카드1에서 카드2로 이동하는 메서드와 현 위치에서 카드1로 이동 -> 카드1에서 카드2로 이동하는 메서드를 만들었다. 이 메서드들은 {최소 이동 횟수, 도착지점 x좌표, 도착지점 y좌표}를 반환하게 했다.
카드쌍에대한 탐색은 recursion()메서드를 통해서 구현했다. 위에서 구현한 카드이동 메서드를 이용해서 이동한 후, 탐색한 카드가 있었던 위치의 값 0으로 바꾸고, 재귀를 실행한다. 실행후에는 최소값을 구하고 탐색한 카드가 있었던 위치의 값을 원래대로 복구한다. 최소이동 횟수에 enter 조작횟수를 더해서 반환한다.
import java.util.*;
class Solution {
public int solution(int[][] board, int r, int c) {
Map<Integer, Card> map = new HashMap<>();
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board.length; j++){
int p = board[i][j];
if(p > 0){
if(!map.containsKey(p)) map.put(p, new Card(p));
map.get(p).addCard(new int[]{i, j});
}
}
}
int answer = Integer.MAX_VALUE / 2;
for(int i : map.keySet()){
int minCount1 = recursion(board, map, r, c, map.get(i), 1);
if(minCount1 < answer) answer = minCount1;
int minCount2 = recursion(board, map, r, c, map.get(i), 2);
if(minCount2 < answer) answer = minCount2;
}
return answer;
}
private int recursion(int[][] board, Map<Integer, Card> map, int r, int c, Card card, int choice){
int[] result = (choice == 1) ? card.moveToCard1(board, r, c) : card.moveToCard2(board, r, c);
int answer = Integer.MAX_VALUE / 2;
card.deleted = true;
board[card.card1[0]][card.card1[1]] = 0;
board[card.card2[0]][card.card2[1]] = 0;
for(int i : map.keySet()){
Card nextCard = map.get(i);
if(nextCard.deleted) continue;
int minCount1 = recursion(board, map, result[1], result[2], nextCard, 1);
if(minCount1 < answer) answer = minCount1;
int minCount2 = recursion(board, map, result[1], result[2], nextCard, 2);
if(minCount2 < answer) answer = minCount2;
}
board[card.card1[0]][card.card1[1]] = card.num;
board[card.card2[0]][card.card2[1]] = card.num;
card.deleted = false;
if(answer == Integer.MAX_VALUE / 2) answer = 0;
return result[0] + answer + 2;
}
private int move(int[][] board, int[] start, int[] end){
int size = 4;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{start[0], start[1], 0});
boolean[][] visited = new boolean[size][size];
visited[start[0]][start[1]] = true;
while(!queue.isEmpty()){
int[] point = queue.poll();
int p1 = point[0];
int p2 = point[1];
int count = point[2];
if(end[0] == p1 && end[1] == p2) return count;
if(p1 > 0) {
int c1 = p1 - 1;
moveOneStep(queue, visited, c1, p2, count + 1);
while(board[c1][p2] == 0 && c1 > 0) c1--;
moveOneStep(queue, visited, c1, p2, count + 1);
}
if(p1 < size - 1) {
int c1 = p1 + 1;
moveOneStep(queue, visited, c1, p2, count + 1);
while(board[c1][p2] == 0 && c1 < size - 1) c1++;
moveOneStep(queue, visited, c1, p2, count + 1);
}
if(p2 > 0) {
int c2 = p2 - 1;
moveOneStep(queue, visited, p1, c2, count + 1);
while(board[p1][c2] == 0 && c2 > 0) c2--;
moveOneStep(queue, visited, p1, c2, count + 1);
}
if(p2 < size - 1) {
int c2 = p2 + 1;
moveOneStep(queue, visited, p1, c2, count + 1);
while(board[p1][c2] == 0 && c2 < size - 1) c2++;
moveOneStep(queue, visited, p1, c2, count + 1);
}
}
return Integer.MAX_VALUE / 2;
}
private void moveOneStep(Queue<int[]> queue, boolean[][] visited, int c1, int c2, int count){
if(!visited[c1][c2]) queue.add(new int[]{c1, c2, count});
visited[c1][c2] = true;
}
private class Card{
int num;
int[] card1;
int[] card2;
boolean deleted = false;
public Card(int num){
this.num = num;
}
public void addCard(int[] card){
if(card1 == null) card1 = card;
else card2 = card;
}
int[] moveToCard1(int[][] board, int r, int c){
int[] p = new int[]{r, c};
int m11 = move(board, p, card1);
int m12 = move(board, card1, card2);
int m1 = m11 + m12;
return new int[]{m1, card2[0], card2[1]};
}
int[] moveToCard2(int[][] board, int r, int c){
int[] p = new int[]{r, c};
int m21 = move(board, p, card2);
int m22 = move(board, card2, card1);
int m2 = m21 + m22;
return new int[]{m2, card1[0], card1[1]};
}
}
}