카드 짝 맞추기

문제

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

코드

import java.util.*;

class Solution {
    static int count = 0;
    static int min = 2000000000;
    int mv[][] = {
        {-1, 0},
        {0, 1},
        {1,0},
        {0,-1}
    };

    class Node{
        int row;
        int col;
        int depth;
        public Node(int row, int col){
            this.row = row;
            this.col = col;
            this.depth = 0;
        }
        public Node(int row, int col, int depth){
            this.row = row;
            this.col = col;
            this.depth = depth;
        }
    }

    int bfs(int[][] board, Node sp, Node ep){
        int min_val = 2000000000;
        int his[][] = new int[4][4];
        Queue<Node> q = new LinkedList<>();
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                his[i][j] = 2000000000;
            }
        }
        his[sp.row][sp.col] = 0;
        q.add(new Node(sp.row, sp.col, 0));
        while(!q.isEmpty()){
            Node cur_node = q.poll();
            int c_r = cur_node.row;
            int c_c = cur_node.col;
            int c_d = cur_node.depth;
            if(cur_node.row == ep.row && cur_node.col == ep.col){
                min_val = Math.min(min_val, his[cur_node.row][cur_node.col]);
                continue;
            }


            for(int i=0; i<4; i++){
                int n_r = c_r + mv[i][0];
                int n_c = c_c + mv[i][1];
                int n_d = c_d + 1;
                if(4 <= n_r || n_r < 0 || 4 <= n_c || n_c < 0)
                    continue;
                else if(his[n_r][n_c] <= n_d)
                    continue;
                his[n_r][n_c] = n_d;
                q.add(new Node(n_r, n_c, n_d));
            }

            for(int i=0; i<4; i++){
                int n_r = c_r + mv[i][0];
                int n_c = c_c + mv[i][1];
                int n_d = c_d + 1;
                while(!(4 <= n_r || n_r < 0 || 4 <= n_c || n_c < 0) && (board[n_r][n_c] == 0)){
                    n_r += mv[i][0];
                    n_c += mv[i][1];
                }
                if(4 <= n_r || n_r < 0 || 4 <= n_c || n_c < 0){
                    n_r -= mv[i][0];
                    n_c -= mv[i][1];
                }
                if(his[n_r][n_c] <= n_d)
                    continue;
                his[n_r][n_c] = n_d;
                q.add(new Node(n_r, n_c, n_d));
            }
        }
        return min_val;
    }


    void dfs(int N, int board[][], int type_arr[], ArrayList<Node> cards[], 
             ArrayList<Node> cur_list, boolean check[], int cur_depth){
        if(cur_depth == N){
            int sum = 0;
            int b_copy[][] = new int[4][4];
            for(int i=0; i<4; i++){
                for(int j=0; j<4; j++)
                    b_copy[i][j] = board[i][j];
            }
            for(int i=0; i<cur_list.size()-1; i++){
                if(i == 0){
                    sum += bfs(b_copy, cur_list.get(i), cur_list.get(i+1));
                }else{
                    int tmp = bfs(b_copy, cur_list.get(i), cur_list.get(i+1));
                    sum += (tmp);
                    b_copy[cur_list.get(i).row][cur_list.get(i).col] = 0;
                    b_copy[cur_list.get(i+1).row][cur_list.get(i+1).col] = 0;
                }
            }
            sum += type_arr.length*2;
            min = Math.min(min, sum);

        }else{
            for(int i=0; i<N; i++)
                if(check[i] == false){
                    check[i] = true;
                    int cur_num = type_arr[i];
                    for(int j=0; j<2; j++){
                        cur_list.add(cards[cur_num].get((0+j)%2));
                        cur_list.add(cards[cur_num].get((1+j)%2));
                        dfs(N, board, type_arr, cards, cur_list, check, cur_depth+1);
                        cur_list.remove(cur_list.size()-1);
                        cur_list.remove(cur_list.size()-1);
                    }
                    check[i] = false;
                }
        }
    }


    public int solution(int[][] board, int r, int c) {
        int answer = 0;
        ArrayList<Node> cards[] = new ArrayList[7];
        HashSet<Integer> types = new HashSet<>();
        ArrayList<Node> cur_list = new ArrayList<>();
        for(int i=1; i<=6; i++)
            cards[i] = new ArrayList<Node>();

        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[i].length; j++)
                if(board[i][j] != 0){
                    cards[board[i][j]].add(new Node(i,j));
                    types.add(board[i][j]);
                }
        }

        int type_arr[] = new int[types.size()];
        boolean check[] = new boolean[types.size()];
        int cursor = 0;
        Iterator<Integer> it = types.iterator();
        while(it.hasNext()){
            type_arr[cursor++] = it.next();
        }

        cur_list.add(new Node(r,c));
        dfs(type_arr.length, board, type_arr, cards, cur_list, check, 0);
        answer = min;
        return answer;
    }
}

피드백

• 다시 푼 문제이다.

• 문제는 2 파트로 나눌 수 있다.

  • 카드 ID 순열을 만드는 부분 , 이 부분에서 각 ID 별로 셔플도 해준다.
    • 이 파트는 그냥 dfs 해줬다.
  • 각 카드 사이의 최소 조작수를 구하는 부분
    • 그냥 row + col 하기에는 저 멀리 카드를 타고 돌아와서 최단거리를 만드는 경우가 있을 수 있기에 모든 경우를 탐색해야 겠다싶어 bfs를 했다.

• 복잡도는 식으로 나타내기는 뭐하고 대충 (6! * 2^6) * ((12 * 16) * 12) = 106168320 정도 나온다.

  • 사실 bfs 부분이 좀 애매했다. 총 칸은 16칸이고 단순히 네 방향으로 움직이는 것과 더불어 점프 하는 경우에 점프 할 자리를 찾는 것까지 더해서 4 + 8 = 12라고 했고 그러면 1억이 넘는데, 만약 그냥 후보지에 마스킹을 하고 큐에 넣는 것만 고려하면 (6! * 2^6) * ((8 * 16) * 12) = 70778880 정도 나온다.
  • 일단 시도해봤더니 TLE는 안나서 통과.

• 처음 시도했을땐 어떻게 최적의 카드를 탐색 순서를 찾지 했는데 이를 그냥 완탐해서 만드는 것에 충격을 먹었었다. 다시 보니 뭐가 최적일지 모르니 그냥 완탐하는게 가장 현명한 선택이었던것 같다.