퍼즐 조각 채우기

네이버 기출

문제 해결 전

1. 일단, game_board에서는 0인칸, table에서는 1인칸을 bfs 탐색해야하기 때문에 동일하게 bfs탐색해주기 위해 편의상 game_board의 0을 1로, 1을 0으로 바꿔준다.

2. 그리고 도형이 동일한지를 확인하기 위해 hash를 이용하는데, 이 때 String으로 hash를 비교하면 도형이 같은지 판단할 수 있기 때문에, 1과 0으로 이루어진 도형을 String으로 바꿔준다. 줄바꿈이 일어날 때는 "n"을 추가한다.

솔루션 세분화 부수적인(?) 필요한 메서드 ① makeString(int mX,MX,mY,My, LinkedList<Point> list) : 도형=>문자열로 만든다. ② rotate() : 2차원 배열을 회전시킨다.

1. game_board 값 변환(0->1, 1->0)

2. game_board bfs 탐색해서 채워야하는 도형(key), Point(갯수,크기)를 (value)로 하는 Map을 완성한다. (i,j)에서 시작, bfs 탐색하면서 탐색했던 좌표들을 리스트에 저장하여 이것을 String으로 변환하는 makeString메서드에 넘겨준다. (i,j)에서 시작한 bfs로 도형을 만들어내는데, 이 때, (x,y)의 최댓값과 최솟값을 각각 구해서, 도형 크기에 맞는 배열을 생성할 수 있다. - maX,minX,maxY,minY도 makeString메서드에 함께 넣어준다.

3. table을 총 4번 회전시킨다. 2에서와 마찬가지로 bfs하면서 String으로 도형을 만들고, HashMap에 존재하면 갯수 감소시키고, 크기만큼 정답에 더해준다!

bfs 탐색한 도형의 좌표를 리스트에 담아서 makeString에 넘긴다. makeString은ㄴ (x,y)의 최솟값과 최댓값을 이용해서 배열의 크기를 만들 수 있고, 최솟값(x,y)인 minX, minY를 이용해서 리스트에 저장된 도형의 좌표값들로부터 minX, minY를 뺌으로써 (0,0)부터 시작한는 도형을 그려낼 수 있다!

String makeString(int minX, int minY, int maxX, int maxY, ArrayList<Point> block) {
        int[][] blockArr = new int[maxX - minX + 1][maxY - minY + 1];
        for (Point p : block)
            blockArr[p.x - minX][p.y - minY] = 1;
        String blockString = "";
        for (int i = 0; i < blockArr.length; i++) {
            for (int j = 0; j < blockArr[0].length; j++)
                blockString += blockArr[i][j];
            blockString += "n";
        }
        return blockString;
    }