99클럽 코테 스터디 11일차 TIL: [프로그래머스] 퍼즐 조각 채우기

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

프로그래머스

 

예전에 풀다가 빡구현에 지쳐서 포기한 문제인데 이번엔 풀었다..! 아이디어 자체는 간단하다.

• bfs를 통해 퍼즐과 빈칸들을 찾는다. 그리고 나중에 빈칸에 퍼즐을 넣을 수 있는지 비교해야 하므로 퍼즐과 빈칸의 위치를 0, 0을 시작으로 하며, 딱 맞는 크기의 배열로 만들어야 한다.
• 그리고 각 빈칸에 각 퍼즐들이 들어갈 수 있는지 확인한다. 
  • 빈칸과 퍼즐의 사이즈는 딱 맞아야 한다.
  • 즉, 두 배열의 가로, 세로 길이가 같아야 한다. 그리고 모든 배열 안의 값이 같아야 한다.
  • 위 두개의 조건을 모두 만족해야 딱 맞다고 할 수 있다. 

아이디어는 간단한데 빡구현이라 어려웠다.. 그리고 내가 실수했던 부분은 다음과 같다.

• 만약 빈칸에 퍼즐이 딱 맞아서 채워 넣었으면, puzzleList에서 해당 퍼즐을 지워줘야 한다. 다음 빈칸들에 퍼즐을 채울 때 이미 빈칸을 채우는데 사용한 퍼즐은 제외해야 하기 때문이다.

import java.util.*;


class Solution {

    int n;
    int[][] game_board;
    int[][] table;
    boolean[][] visited_table;
    boolean[][] visited_board;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    List<int[][]> puzzleList = new ArrayList<>();
    List<int[][]> boardList = new ArrayList<>();
    int answer;
    
    public int solution(int[][] game_board, int[][] table) {

        this.game_board = game_board;
        this.table = table;
        n = game_board.length;
        visited_table = new boolean[n][n];
        visited_board = new boolean[n][n];

        // 1. bfs로 퍼즐 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] == 1 && !visited_table[i][j]) {
                    bfsForPuzzle(i, j);
                }
            }
        }

        // 2. bfs로 게임 보드의 빈 칸 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (game_board[i][j] == 0 && !visited_board[i][j]) {
                    bfsForBoard(i, j);
                }
            }
        }

        // 3. 보드에 퍼즐 넣기
        for (int[][] board : boardList) {
            for (int[][] puzzle : puzzleList) {
                boolean isPut = putPuzzle(board, puzzle);
                if (isPut) {
                    puzzleList.remove(puzzle);
                    break;
                }
            }
        }

        return answer;
    }

    public void bfsForPuzzle(int y, int x) {
        List<Node> list = new ArrayList<>();
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(y, x));
        visited_table[y][x] = true;
        list.add(new Node(y, x));
        int minX = x;
        int minY = y;
        int maxX = x;
        int maxY = y;

        while (!que.isEmpty()) {
            Node now = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + now.x;
                int ny = dy[i] + now.y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || table[ny][nx] != 1 || visited_table[ny][nx]) {
                    continue;
                }
                que.add(new Node(ny, nx));
                visited_table[ny][nx] = true;
                list.add(new Node(ny, nx));
                minX = Math.min(minX, nx);
                maxX = Math.max(maxX, nx);
                minY = Math.min(minY, ny);
                maxY = Math.max(maxY, ny);
            }
        }

        // list에 있는 값들을 통해 딱 맞는 배열 만들기 (퍼즐 위치한 곳 = 1)
        int[][] puzzle = new int[maxY - minY + 1][maxX - minX + 1];
        for (Node node : list) {
            puzzle[node.y - minY][node.x - minX] = 1;
        }

        puzzleList.add(puzzle);
    }

    public void bfsForBoard(int y, int x) {
        List<Node> list = new ArrayList<>();
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(y, x));
        visited_board[y][x] = true;
        list.add(new Node(y, x));
        int minX = x;
        int minY = y;
        int maxX = x;
        int maxY = y;

        while (!que.isEmpty()) {
            Node now = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + now.x;
                int ny = dy[i] + now.y;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || game_board[ny][nx] != 0 || visited_board[ny][nx]) {
                    continue;
                }
                que.add(new Node(ny, nx));
                visited_board[ny][nx] = true;
                list.add(new Node(ny, nx));
                minX = Math.min(minX, nx);
                maxX = Math.max(maxX, nx);
                minY = Math.min(minY, ny);
                maxY = Math.max(maxY, ny);
            }
        }

        // list에 있는 값들을 통해 딱 맞는 배열 만들기 (빈 칸 = 1)
        int[][] board = new int[maxY - minY + 1][maxX - minX + 1];
        for (Node node : list) {
            board[node.y - minY][node.x - minX] = 1;
        }

        boardList.add(board);
    }

    private boolean putPuzzle(int[][] board, int[][] puzzle) {
        for (int i = 0; i < 4; i++) {
            if (canPut(board, puzzle)) {
                return true;
            } else {
                puzzle = turn(puzzle); 
            }
        }
        return false;
    }
    
    private boolean canPut(int[][] board, int[][] puzzle) {
        // 1. 사이즈가 맞는지
        int boardY = board.length;
        int boardX = board[0].length;
        int puzzleY = puzzle.length;
        int puzzleX = puzzle[0].length;

        if ((boardY != puzzleY) || (boardX != puzzleX)) {
            return false;
        }

        // 2. 퍼즐 위치와 빈칸의 위치가 맞는지
        int cnt = 0;
        for (int i = 0; i < boardY; i++) {
            for (int j = 0; j < boardX; j++) {
                if (board[i][j] != puzzle[i][j]) {
                    return false;
                }
                if (puzzle[i][j] == 1) {
                    cnt++;
                }
            }
        }

        answer += cnt;
        return true;
    }

    // 회전한 새로운 배열을 만들어서 반환
    private int[][] turn(int[][] puzzle) {
        int[][] newPuzzle = new int[puzzle[0].length][puzzle.length];
        for (int i = 0; i < puzzle.length; i++) {
            for (int j = 0; j < puzzle[0].length; j++) {
                if (puzzle[i][j] == 1) {
                    newPuzzle[j][puzzle.length - i - 1] = 1;
                }
            }
        }
        return newPuzzle;
    }

    public class Node {

        int y, x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}