[Programmers] 퍼즐 조각 채우기 (Java)

1.  문제 링크

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

2.  문제

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

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

다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

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

3.  제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

입출력 예

4.  소스코드

import java.util.*;

class Solution {
    int maxX, minX, maxY, minY;
    ArrayList<Puzzle> blanks, puzzles;
    int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    public int solution(int[][] game_board, int[][] table) {
        makeBlankList(game_board);
        makePuzzleList(table);

        int answer = 0;
        boolean[] visited = new boolean[puzzles.size()];
        for(int blankIdx = 0; blankIdx < blanks.size(); blankIdx++) {
            for(int puzzleIdx = 0; puzzleIdx < puzzles.size(); puzzleIdx++) {
                if(!visited[puzzleIdx]) {
                    int count = matchPuzzleToBlank(blankIdx, puzzleIdx, visited);
                    answer += count;
                    if(count > 0) break;
                }
            }
        }

        return answer;
    }

    public int countMatching(int[][] blank, int[][] puzzle) {
        if (blank.length != puzzle.length || blank[0].length != puzzle[0].length) return 0;

        int count = 0;
        for (int row = 0; row < blank.length; row++) {
            for (int col = 0; col < blank[0].length; col++) {
                if (blank[row][col] != puzzle[row][col]) return 0;
                if (puzzle[row][col] == 1) count++;
            }
        }

        return count;
    }

    public int matchPuzzleToBlank(int blankIdx, int puzzleIdx, boolean[] visited) {
        int count = countMatching(blanks.get(blankIdx).puzzle, puzzles.get(puzzleIdx).puzzle);
        if(count != 0) {
            visited[puzzleIdx] = true;
            return count;
        }

        count = countMatching(blanks.get(blankIdx).puzzle, puzzles.get(puzzleIdx).rotate90());
        if(count != 0) {
            visited[puzzleIdx] = true;
            return count;
        }

        count = countMatching(blanks.get(blankIdx).puzzle, puzzles.get(puzzleIdx).rotate180());
        if(count != 0) {
            visited[puzzleIdx] = true;
            return count;
        }

        count = countMatching(blanks.get(blankIdx).puzzle, puzzles.get(puzzleIdx).rotate270());
        if(count != 0) {
            visited[puzzleIdx] = true;
            return count;
        }

        return 0;
    }

    public boolean isInMap(int x, int y, int[][] table) {
        if(x >= 0 && x < table.length && y >= 0 && y < table[0].length) return true;
        return false;
    }

    public void makePuzzleList(int[][] table) {
        boolean[][] visited = new boolean[table.length][table[0].length];
        ArrayList<int[]> list = new ArrayList<>();
        puzzles = new ArrayList<>();

        for(int row = 0; row < table.length; row++) {
            for(int col = 0; col < table[row].length; col++) {
                if(!visited[row][col] && table[row][col] == 1) {
                    list = new ArrayList<>();
                    list.add(new int[] {row, col});
                    maxX = minX = row;
                    maxY = minY = col;
                    visited[row][col] = true;
                    dfs(row, col, 1, visited, table, list);

                    Puzzle puzzle = new Puzzle();
                    puzzle.puzzle = new int[maxX - minX + 1][maxY - minY + 1];

                    for(int[] elem : list)
                        puzzle.puzzle[elem[0] - minX][elem[1] - minY] = 1;

                    puzzles.add(puzzle);
                }
            }
        }
    }

    public void makeBlankList(int[][] game_board) {
        boolean[][] visited = new boolean[game_board.length][game_board[0].length];
        ArrayList<int[]> list = new ArrayList<>();
        blanks = new ArrayList<>();

        for(int row = 0; row < game_board.length; row++) {
            for(int col = 0; col < game_board[row].length; col++) {
                if(!visited[row][col] && game_board[row][col] == 0) {
                    list = new ArrayList<>();
                    list.add(new int[] {row, col});
                    maxX = minX = row;
                    maxY = minY = col;
                    visited[row][col] = true;
                    dfs(row, col, 0, visited, game_board, list);

                    Puzzle puzzle = new Puzzle();
                    puzzle.puzzle = new int[maxX - minX + 1][maxY - minY + 1];

                    for(int[] elem : list)
                        puzzle.puzzle[elem[0] - minX][elem[1] - minY] = 1;

                    blanks.add(puzzle);
                }
            }
        }
    }

    public void dfs(int x, int y, int target, boolean[][] visited, int[][] arr, ArrayList<int[]> list) {
        for(int dir = 0; dir < dx.length; dir++) {
            int cx = x + dx[dir], cy = y + dy[dir];

            if(isInMap(cx, cy, arr)) {
                if(!visited[cx][cy] && arr[cx][cy] == target) {
                    visited[cx][cy] = true;
                    list.add(new int[] {cx, cy});
                    maxX = Math.max(maxX, cx);
                    minX = Math.min(minX, cx);
                    maxY = Math.max(maxY, cy);
                    minY = Math.min(minY, cy);
                    dfs(cx, cy, target, visited, arr, list);
                }
            }
        }
    }

    class Puzzle {
        int[][] puzzle;

        int[][] rotate90() {
            int[][] rotate = new int[puzzle[0].length][puzzle.length];

            for(int row = 0; row < puzzle.length; row++) {
                for(int col = 0; col < puzzle[0].length; col++) {
                    rotate[col][(puzzle.length - 1) - row] = puzzle[row][col];
                }
            }

            return rotate;
        }

        int[][] rotate180() {
            int[][] rotate = new int[puzzle.length][puzzle[0].length];

            for(int row = 0; row < puzzle.length; row++) {
                for(int col = 0; col < puzzle[0].length; col++) {
                    rotate[(puzzle.length - 1) - row][(puzzle[0].length - 1) - col] = puzzle[row][col];
                }
            }

            return rotate;
        }

        int[][] rotate270() {
            int[][] rotate = new int[puzzle[0].length][puzzle.length];

            for(int row = 0; row < puzzle.length; row++) {
                for(int col = 0; col < puzzle[0].length; col++) {
                    rotate[(puzzle[0].length - 1) - col][row] = puzzle[row][col];
                }
            }

            return rotate;
        }
    }
}

5.  접근

• 각 빈칸 및 퍼즐 조각을 나타내는 Puzzle 클래스를 정의합니다.
  • 2차원 배열 puzzle을 멤버 변수로 갖는데, 이는 각 빈칸/퍼즐 조각의 크기에 맞게 2차원 배열을 선언하고 빈칸이면 빈칸인 지점들이, 퍼즐 조각이면 퍼즐이 있는 지점들이 1이라는 값을 갖고 그 반대는 0인 값을 갖습니다.
  • puzzle 배열을 90도, 180도, 270도로 회전시킨 배열을 반환하는 메서드들을 갖습니다.

• 현재 게임 보드의 상태를 나타내는 game_board와 테이블 위에 놓인 퍼즐 조각의 상태를 나타내는 table 배열에 대해 각각 DFS를 활용하여 빈칸들 및 퍼즐 조각들을 구합니다.
• 각 빈칸에 맞는 퍼즐 조각을 찾아 총 몇 칸을 채울 수 있는지 구합니다.
  • 빈칸을 채우는 데에 사용한 퍼즐 조각들에 대해 방문 체크를 진행하면서 각 빈칸을 채워나갑니다.
  • 만약 퍼즐 조각을 그대로 이용하여 빈칸을 채울 수 없다면, 90도로 돌린 경우, 180도로 돌린 경우, 270도로 돌린 경우 각각에 대해 순서대로 빈칸과 맞춰보고, 그 중 맞는 경우가 있다면 채운 빈칸의 개수를 반환하고 해당 퍼즐에 대해 방문 체크를 진행합니다.
  • 반환한 채운 빈칸의 개수들을 더해나갑니다.