퍼즐 조각 채우기 (위클리 챌린지 3주차)

문제

https://programmers.co.kr/learn/courses/30/lessons/84021#

코드

import java.util.*;


class Solution {

    int max_idx;
    int max_val = -1;

    int mv[][] = {
        {-1,0},
        {0,1},
        {1,0},
        {0,-1}
    };

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

    private Vector<Integer> mark_table(int[][] table){
        boolean[][] visit = new boolean[table.length][table.length];
        Vector<Integer> size_v = new Vector<>();

        for(int i=0; i<visit.length; i++){
            for(int j=0; j<visit.length; j++)
                visit[i][j] = false;
        }
        int cur_id = 1;
        for(int i=0; i<table.length; i++){
            for(int j=0; j<table.length; j++){
                if(table[i][j] == 1 && visit[i][j] == false){
                    int size;
                    size = mark_id(table, visit, i, j ,cur_id);
                    size_v.add(size);
                    cur_id++;
                }
            }
        }
        max_idx = cur_id;
        return size_v;
    }

    private int mark_id(int[][] table, boolean[][] visit, int s_r, int s_c, int cur_id){
        Queue<Node> q = new LinkedList<>();
        visit[s_r][s_c] = true;
        q.add(new Node(s_r, s_c));
        int cur_size = 0;
        while(!q.isEmpty()){

            Node cur_node = q.peek();
            q.poll();
            int c_r = cur_node.row;
            int c_c = cur_node.col;
            cur_size++;
            table[cur_node.row][cur_node.col] = cur_id;

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

        }

        return cur_size;

    }

    private Vector<String> make_map_str(int[][] game_board){

        boolean visit[][] = new boolean[game_board.length][game_board.length];

        for(int i=0; i<visit.length; i++){
            for(int j=0; j<visit.length; j++){
                visit[i][j] = false;
            }
        }
        Vector<String> board_v = new Vector<>();

        for(int i=0; i<game_board.length; i++){
            for(int j=0; j<game_board.length; j++){
                if(visit[i][j] == false && game_board[i][j] == 0)
                    board_v.add(dfs_str(game_board, visit, game_board[i][j], i, j, 0, 0));
            }
        }

        return board_v;

    }

    private void make_table_str(Vector<String>[] table_map, int[][] game_board){

        boolean visit[][] = new boolean[game_board.length][game_board.length];

        for(int i=0; i<visit.length; i++){
            for(int j=0; j<visit.length; j++){
                visit[i][j] = false;
            }
        }
        Vector<String> board_v = new Vector<>();

        for(int i=0; i<game_board.length; i++){
            for(int j=0; j<game_board.length; j++){
                if(visit[i][j] == false && game_board[i][j] != 0){
                    String tmp = dfs_str(game_board, visit, game_board[i][j], i, j, 0, 0);
                    table_map[game_board[i][j]].add(tmp);
                }
            }
        }

    }

    private String dfs_str(int[][] game_board, boolean[][] visit, int cur_val, int s_r, int s_c, int r_o, int c_o){

        String res = "#" + Integer.toString(r_o) + "," + Integer.toString(c_o);
        visit[s_r][s_c] = true;
        for(int i=0; i<4; i++){
            int n_r = s_r + mv[i][0];
            int n_c = s_c + mv[i][1];
            if(game_board.length <= n_r || n_r < 0 || game_board.length <= n_c || n_c < 0)
                continue;
            else if(game_board[n_r][n_c] != cur_val)
                continue;
            else if(visit[n_r][n_c] == true)
                continue;
            res += this.dfs_str(game_board, visit, cur_val, n_r, n_c, r_o+mv[i][0], c_o+mv[i][1]);
        }
        return res;

    }

    private int[][] rotate_arr(int[][] table){
        int N = table.length;
        int copy_arr[][] = new int[table.length][table.length];
        for(int i=0; i<table.length; i++){
            for(int j=0; j<table.length; j++)
                copy_arr[i][j] = table[N-j-1][i];
        }
        return copy_arr;
    }

    public int solution(int[][] game_board, int[][] table) {
        int answer = -1;
        Vector<Integer> size_v = this.mark_table(table);        

        this.make_map_str(game_board);


        Vector<String> board_map = this.make_map_str(game_board);
        Vector<String> block_map[] = new Vector[max_idx+1];
        for(int i=0; i<block_map.length; i++)
            block_map[i] = new Vector<>();


        for(int i=0; i<4; i++){
            this.make_table_str(block_map, table);
            table = this.rotate_arr(table);
        }

        HashMap<String, Vector<Integer>> s_idx = new HashMap<>();

        for(int i=1; i<block_map.length; i++){
            for(String str : block_map[i]){
                if(s_idx.get(str) == null){
                    s_idx.put(str, new Vector<Integer>());
                }
                s_idx.get(str).add(i);
            }
        }


        boolean check[] = new boolean[max_idx+1];
        for(int i=0; i<check.length; i++)
            check[i] = false;

        answer = 0;
        System.out.println("board_map.size() : " + board_map.size() + ", size_v.size() : " + size_v.size());
        for(int k=0; k<board_map.size(); k++){
            String board_str = board_map.get(k);
            if(s_idx.get(board_str) != null){
                Vector<Integer> tmp_v = s_idx.get(board_str);
                for(Integer idx : tmp_v){
                    if(check[idx])
                        continue;
                    else{
                        check[idx] = true;
                        try{
                        answer += size_v.get(idx-1);
                        }catch(Exception e){
                            System.out.println("nope");
                        }
                        break;
                    }
                }
            }
        }

        return answer;
    }
}

피드백

• 위 코드의 알고리즘은 크게 다음과 같다.

  1. gameboard의 빈칸을 문자열로 파씽한다.
  2. table의 블록들을 돌려가며 문자열로 파씽한다.
  3. hash table을 이용하여 gameboard의 빈칸이 table의 블록중 하나와 매칭될 수 있는지 확인한다.
     3-1. 매칭된다면 check하여 다시 사용못하게 한다. 그리고 answer에 크기를 더한다.

• 문자열로 파씽하는데 #${row},${col}과 같은 식으로 좌표와 row,col을 구분하여 데이터가 손실되지 않도록 한다. 구분하지 않는다면 데이터가 손실되어 제대로 된 결과가 나올 수 없을 것이다.

• 처음에는 dfs를 사용하여 최대의 값을 나오게 했다. 근데 그럴필요가 없다. 그냥 매칭되는 아이만 찾아서 매칭해주면 되기 때문. 그리서 반복문과 hash table을 사용하여 sol을 바꾸었다. gameboard의 빈칸 갯수를 N, table의 블록 갯수를 M이라고 하면 O(N*M)이 나온다.