2021 Kakao blind - 카드 짝 맞추기(bfs, recursion) - java 풀이

https://programmers.co.kr/learn/courses/30/lessons/72415

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

- 2차원 배열 board의 크기가 4*4 이고, 카드 종류는 1~6, board에 존재하는 카드 페어는 무조건 1짝 씩 있다는 점이 주요 포인트이다.
카드의 갯수가 최대 12개 이고, 카드 1종류를 정해서 최단거리로 소거해나간다면 순회 순서를 순열로 만들어서 순회한다면 순열 복잡도 * bfs 복잡도 = O(n! * V^2) = 6! * 16^2 = 18만 연산으로 최단거리를 구할 수 있다. 

- 아래 풀이는 순열도 만들지 않고 1~6까지 존재하는 카드가 없을 때까지 재귀적으로 board를 모두 순회해나가는 방식으로 작성했다. 이렇게 작성을 해도 O(n^n * V^12) = 6^6 * 16^2 = 1100만 연산으로서 시간제한을 초과하지 않는다.

- 카드 1 페어를 소거할 때 이동방식은
1. 커서 위치 -> 카드1 위치 -> 카드2 위치
2. 커서 위치 -> 카드2 위치 -> 카드 1 위치 일 것이다. 
둘 다 이동거리도 다를 뿐더러 그 다음 카드 페어를 지울 때의 이동거리를 연산 할 때도 이동된 커서 위치가 반영된다. 따라서 재귀적으로 모든 카드를 다 지울 때까지의 이동거리를 모두 합한 값끼리 비교해줘야 한다. 

- bfs 탐색을 할 때도 주의해야할 점은 일반 이동과 ctrl을 이용한 이동 2가지가 존재한다는 점이다. 카드 혹은 끝 칸 까지 이동하는 로직을 작성해야 한다. bfs 탐색시 1칸씩 이동하게 되는데, 이미 방문한 옆 칸은 이동할 수 없어도 ctrl이동으로 그 방향 옆옆칸은 이동할 수 있을 수 도 있으므로 이 부분을 스킵해서는 안된다. 이 부분을 구현하면서 단순히 옆칸은 이동할 수 없네 하고 continue로 다음 방향벡터로 넘어가버리는 바람에 오류를 찾는데 많은 시간을 필요로 했다. 

import java.util.*;

class Solution {
    final int INF = 0x3f3f3f3f;
    int[] dr = {-1, 0, 1, 0};
    int[] dc = {0, 1, 0, -1};
    
    public int solution(int[][] board, int r, int c) {
        return go(board, new int[] {r, c});
    }
    
    int go(int[][] board, int[] src) {
        int ret = INF;
        
        for(int k = 1; k <= 6; ++k) {
            List<int[]> card = new ArrayList<>();
            
            for(int i = 0; i < 4; ++i) {
                for(int j = 0; j < 4; ++j) {
                    if(board[i][j] == k) card.add(new int[] {i, j});
                }
            }
            
            if(card.isEmpty()) continue;
            
            int[] card1 = card.get(0);
            int[] card2 = card.get(1);
            
            int ab = bfs(board, src, card1) + bfs(board, card1, card2) + 2;
            int ba = bfs(board, src, card2) + bfs(board, card2, card1) + 2;
            
            board[card1[0]][card1[1]] = board[card2[0]][card2[1]] = 0;
            int abRecursive = ab + go(board, card2);
            int baRecursive = ba + go(board, card1);
            ret = Math.min(ret, Math.min(abRecursive, baRecursive));
            
            board[card1[0]][card1[1]] = board[card2[0]][card2[1]] = k;
        }
        
        if(ret == INF) return 0;
        return ret;
    }
    
    int bfs(int[][] board, int[] src, int[] dest) {
        Queue<int[]> q = new LinkedList<>();
        int[][] d = new int[4][4];
        for(int i = 0; i < 4; ++i) {
            Arrays.fill(d[i], -1);
        }
        
        q.add(src);
        d[src[0]][src[1]] = 0;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            int r = now[0], c = now[1];
            if(r == dest[0] && c == dest[1]) return d[r][c];
            
            for(int i = 0; i < 4; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if(0 > nr || 0 > nc || 4 <= nr || 4 <= nc) continue;
                if(d[nr][nc] == -1) {
                    d[nr][nc] = d[r][c] + 1;
                    q.add(new int[] {nr, nc});   
                }
                
                for(int j = 0; j < 2; ++j) {
                    if(board[nr][nc] != 0) break;
                    int nnr = nr + dr[i];
                    int nnc = nc + dc[i];
                    if(0 > nnr || 0 > nnc || 4 <= nnr || 4 <= nnc) break;
                    
                    nr = nnr;
                    nc = nnc;
                }
                
                if(d[nr][nc] == -1) {
                    d[nr][nc] = d[r][c] + 1;
                    q.add(new int[] {nr, nc});   
                }
            }
        }
        
        return -1;
    }
}