퍼즐 조각 채우기

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요

조각은 한 번에 하나씩 채워 넣습니다.
조각을 회전시킬 수 있습니다.
조각을 뒤집을 수는 없습니다.
게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

처음 생각한것

이 문제는 생각보다 막막했다. bfs를 통해서 해결한다면 board와 table을 어떻게 비교해야하는가? 처음에는 table의 값을 얻어서 board의 배열 전체를 돌아다니며 비교하는것을 생각했으나 너무 많은 이동이 필요하고 회전까지 해야하기에 적합하지않다.
그러던 도중 규칙중 4번을 보면 보드의 빈칸에 조각을 채워넣었을때 빈칸이 존재하면 안된다면 보드와 조각의 빈부분과 조각형태를 리스트화 시킨 배열로 얻은 후 그것을 비교하기만 하면된다는 것을 알았다.
(아니라면 인접한칸이 생겼을때 또 다시 board의 리스트를 변경해야한다)

또한 회전을 시켜야하지만 이때 회전축을 0,0으로 만들고 시작하면 다른 값을 생각할 필요가 없어진다(90도를 회전시 2차원 배열을 생각했으나 그냥 x y -> y -x가 된다는것을 알아냈다면 간편해진다).

코드

import java.util.*;
class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int solution(int[][] game_board, int[][] table) {
        int size= table.length;
        boolean[][] tVisit = new boolean[size][size];
        boolean[][] gVisit = new boolean[size][size];      
        List<List<int[]>> tList = new ArrayList<>();
        List<List<int[]>> gList = new ArrayList<>();
        //board와 table에서 빈칸과 조각이 놓인칸 분리.
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(!tVisit[i][j]&&table[i][j]==1){
                    bfs(i,j,1,table,tList,tVisit);
                }
                if(!gVisit[i][j]&&game_board[i][j]==0){
                   bfs(i,j,0,game_board,gList,gVisit);
                }
                    
            }
        }
        int answer = comparePuzzle(tList,gList);
       
        return answer;
    }
    int comparePuzzle(List<List<int[]>> tList,List<List<int[]>> gList){
        int result =0;
        boolean[] visit = new boolean[gList.size()];
        for(int i=0;i<tList.size();i++){
            for(int j=0;j<gList.size();j++){
                if(visit[j]||tList.get(i).size()!=gList.get(j).size()) continue;
                if(rotate(tList.get(i),gList.get(j))){
                    visit[j] = true;
                    result += gList.get(j).size();
                    break;
                }
            }
        }
        
        return result;
    }
    boolean rotate(List<int[]> tList,List<int[]> gList){
       boolean result = false;
        //오름차순 정렬
        gList.sort((o1, o2) ->{
            if(o1[0]!=o2[0]){
                return o1[0] - o2[0];
            }else{
                return o1[1] - o2[1];
            }          
        });
        
        for(int i=0;i<4;i++){
            tList.sort((o1, o2) ->{
            if(o1[0]!=o2[0]){
                return o1[0] - o2[0];
            }else{
                return o1[1] - o2[1];
            }          
            });
            int xkey = tList.get(0)[0];
            int ykey = tList.get(0)[1];
            //좌표값을 0,0부터 시작
            for(int j=0;j<tList.size();j++){
                tList.get(j)[0] -= xkey;
                tList.get(j)[1] -= ykey;
            }
            boolean flag = true;
            for(int j=0;j<gList.size();j++){
                if(tList.get(j)[0]!=gList.get(j)[0]||tList.get(j)[1]!=gList.get(j)[1]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                result = true;
                break;
            } else{
                //회전
                 for(int j=0; j<tList.size(); j++){
                    int tmp = tList.get(j)[0];
                    tList.get(j)[0] = tList.get(j)[1];
                    tList.get(j)[1] = -tmp;
                }
            }
        }
        return result;
    }
    void bfs(int x, int y,int type,int[][] board,List<List<int[]>> list, boolean[][] visit){
        visit[x][y] =true;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        List<int[]> tmp = new ArrayList<>();
        tmp.add(new int[]{0,0});
        while(!q.isEmpty()){
            int[] gap = q.poll();
            for(int i=0;i<4;i++){
                int nx = gap[0] + dx[i];
                int ny = gap[1] + dy[i];
                if(nx<0||ny<0||nx>=board.length||ny>=board.length) continue;
                if(board[nx][ny]==type&&!visit[nx][ny]){
                    visit[nx][ny]=true;
                    tmp.add(new int[]{nx-x,ny-y});
                    q.add(new int[]{nx,ny});
                }
            }
            
            
        }
        list.add(tmp);
    }
}

형태를 생각하는것부터 구현까지 쉽지않은 문제였다. bfs와 회전 그리고 퍼즐이 0,0부터 움직이는것을 생각해보자.