[프로그래머스/Java] 퍼즐 조각 채우기

-Code

import java.util.*;

class Solution {
    static class PosInfo {
        int row, col;
        
        public PosInfo (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        int length = game_board.length;
        ArrayList<ArrayList<PosInfo>> peices = getPiecesPos(table);
        boolean[] visited = new boolean[peices.size()];
        // 게임 보드 돌면서 구멍 모양 찾고 검사
        for (int row = 0; row < length; row++) {
            for (int col = 0; col < length; col++) {
                // 구멍인 경우
                if (game_board[row][col] == 0) {
                    ArrayList<PosInfo> hollPos = new ArrayList<>();
                    PosInfo boardPos = new PosInfo(row, col);
                    getPosInfo(0, boardPos, hollPos, game_board);
                    // 매꿀수 있는 경우 구멍의 크기만큼 값 증가
                    if (calcGameBoard(visited, hollPos, peices)) {
                        answer += hollPos.size();
                    }
                }
            }
        }
        return answer;
    }
    // 구멍에 맞는 도형이 있는지 검사
    private static boolean calcGameBoard(
        boolean[] visited, 
        ArrayList<PosInfo> hollPos, 
        ArrayList<ArrayList<PosInfo>> peices
    ) {
        // 구멍 위치 셋팅 및 정렬
        ArrayList<PosInfo> settingHollPos = settingPosInfo(hollPos);
        // 검사
        for (int i = 0; i < peices.size(); i++) {
            // 사용안한 도형이고 들어갈 수 있는지 확인
            if (!visited[i] && isPutIn(settingHollPos, peices.get(i))) {
                visited[i] = true;
                return true;
            }
        }
        return false;
    }
    // 빈 공간에 넣을 수 있는지 확인
    private static boolean isPutIn(
        ArrayList<PosInfo> hollPos, 
        ArrayList<PosInfo> peices
    ) {
        // 도형의 크기가 맞지 않으면 불가능
        if (hollPos.size() != peices.size()) {
            return false;
        }
        ArrayList<PosInfo> rotationPos = peices;
        for (int i = 0; i < 4; i++) {
            // 도형 90도씩 돌려서 확인
            rotationPos = rotation(rotationPos);
            if (isSame(hollPos, rotationPos)) {
                return true;
            }
        }
        return false;
    }
    // 도형 맞는지 확인
    private static boolean isSame(
        ArrayList<PosInfo> hollPos, 
        ArrayList<PosInfo> peices
    ) {
        for (int i = 0; i < hollPos.size(); i++) {
            PosInfo hollInfo = hollPos.get(i);
            PosInfo peiceInfo = peices.get(i);
            if (hollInfo.row != peiceInfo.row || hollInfo.col != peiceInfo.col) {
                return false;
            }
        }
        return true;
    }
    // 도형 회전 시키기
    private static ArrayList<PosInfo> rotation(ArrayList<PosInfo> posInfo) {
        ArrayList<PosInfo> rotationPos = new ArrayList<>();
        // 회전은 row, col일때 col, -row (특정 크기안에 도형이면 n - 1 - row)
        for (PosInfo info : posInfo) {
            PosInfo rotatePos = new PosInfo(info.col, -info.row);
            rotationPos.add(rotatePos);
        }
        return settingPosInfo(rotationPos);
    }
    // 도형들 위치 리스트 얻기
    private static ArrayList<ArrayList<PosInfo>> getPiecesPos(int[][] table) {
        ArrayList<ArrayList<PosInfo>> peices = new ArrayList<>();
        // 테이블을 돌면서 조각들 위치 저장
        for (int row = 0; row < table.length; row++) {
            for (int col = 0; col < table.length; col++) {
                if (table[row][col] == 1) {
                    ArrayList<PosInfo> peicePos = new ArrayList<>();
                    PosInfo start = new PosInfo(row, col);
                    getPosInfo(1, start, peicePos, table);
                    peices.add(settingPosInfo(peicePos));
                }
            }
        }
        return peices;
    }
    // 조각 위치 셋팅 및 정렬
    // 조각 위치 셋팅 및 정렬해야 구하기 쉬움
    // 시작점을 같게 할 수 있기 때문에
    private static ArrayList<PosInfo> settingPosInfo(
        ArrayList<PosInfo> posInfo
    ) {
        // 셋팅 후 반환할 리스트
        ArrayList<PosInfo> settingPos = new ArrayList<>();
        // 최소 row, col 구하기
        int minRow = Integer.MAX_VALUE;
        int minCol = Integer.MAX_VALUE;
        for (PosInfo info : posInfo) {
            minRow = Math.min(info.row, minRow);
            minCol = Math.min(info.col, minCol);
        }
        // 최소 row, col을 뺀후 저장
        for (PosInfo info : posInfo) {
            int newRow = info.row - minRow;
            int newCol = info.col - minCol;
            PosInfo newInfo = new PosInfo(newRow, newCol);
            settingPos.add(newInfo);
        }
        // 정렬 후 반환
        settingPos.sort((o1, o2) -> {
            return o1.row == o2.row ? o1.col - o2.col : o1.row - o2.row;
        });
        return settingPos;
    }
    
    // 도형 위치값 찾기
    private static void getPosInfo(
        int val, 
        PosInfo posInfo, // 탐색 시작 위치
        ArrayList<PosInfo> posList, // 위치 저장할 리스트
        int[][] board // 탐색할 배열
    ) {
        // 방문 처리
        // game_board와 table에 같이 사용함으로 val에 따른 방문 처리
        board[posInfo.row][posInfo.col] = val == 1 ? 0 : 1;
        posList.add(posInfo);
        // 이동 방향
        int[] dRow = {-1, 1, 0, 0};
        int[] dCol = {0, 0, -1, 1};
        // 탐색
        for (int i = 0; i < 4; i++) {
            int nextRow = posInfo.row + dRow[i];
            int nextCol = posInfo.col + dCol[i];
            // 범위안이고 주어진 값과 일치하는 경우 탐색
            // table이면 1일때 탐색, game_board면 0일때 탐색
            if (canMove(nextRow, nextCol, board.length) && 
                board[nextRow][nextCol] == val) {
                PosInfo next = new PosInfo(nextRow, nextCol);
                getPosInfo(val, next, posList, board);
            }
        }
    }
    // 움직일 수 있는 위치인지 확인
    private static boolean canMove(int row, int col, int size) {
        return (0 <= row && row < size) && (0 <= col && col < size);
    }
}

처음 봤을 때는 이해하기 쉽지 않았고, 구현할 엄두가 나지 않아서 몇 가지 힌트를 얻고 다음날 풀기로 하고 시도해 봤습니다.

받은 힌트로는 아래와 같습니다.

1. 도형들을 dfs로 위치값을 구해서 리스트로 저장해서 탐색해야 합니다.
2. 위치값을 구할 때, 최솟값들로 빼주어서 시작점을 같은 곳에서 할 수 있도록하고 정렬해서 하면 순서도로 비교가 가능하다.
3. 도형을 돌리는 방법은 (row, col)일때 (col, -row)으로 음수가 나올 수 있지만 위에서 사용한 최솟값 빼는 로직으로 음수가 나와도 해결 가능하다.

이 3가지를 힌트를 처음에는 이게 구현이 될까 했지만 하나하나 구현을 해보니 되기는 했습니다. 하지만 구멍과 도형 비교에 list.equals를 사용했는데 이상하게 나와 찾아보니 저는 객체를 사용해서 했기 때문에 isSame이란 메서드를 다시 만들어 해결했습니다. 그리고 문제가 길다 보니 도형이 들어갈 때마다 1개씩 증가인 줄 알았지만 도형의 크기만큼 증가라 이 부분도 수정해서 해결했습니다.

❗도형 돌리기 참고
원래 돌리는 로직은 (col, arr.length - 1 - row)이나 이 문제의 경우 도형을 구성하는 점 하나하나를 원점을 중심으로 회전시키는 방식이기 때문에 (col -row)로 돌리게 됩니다.