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

출처

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

프로그래머스

문제

 

game_board의 빈공간에, table에 주어진 도형을 끼워 맞추는 문제이다. 도형은 회전시킬 수 있지만, 뒤집을 수는 없다.

이때, 최대 몇칸을 채워넣을 수 있는지 구하는 문제이다.

 

풀이

BFS를 이용하여 풀 수 있는 문제이다. 상당히 코드도 길고 어려울 수 있지만, 다음과 같은 과정을 따라가면 된다.

 

먼저, BFS 알고리즘을 이용하여 board의 빈 공간과 table에 주어진 모양을 추출한다. 빈 공간과 table의 모양만을 체크하기 위하여, 먼저 탐색이 시작된 한 점을 (0, 0)으로 놓고 나머지 블록들은 기준이 되는 시작점과 상대적인 위치 차이의 정보(지금 블록의 좌표 - 시작지점 좌표)만 저장하도록 한다.

ex) (1, 1), (1, 2), (2, 1) 모양의 블록 -> (0, 0), (0, 1), (0, 2) 로 저장

 

 

다음, 추출한 board의 블록들을 table의 빈공간과 하나씩 비교하여 딱 맞으면 table에 있는 도형을 사용하였는지 체크할 visited 배열을 true로 바꿔주고(중복 방지) 블록의 칸수 만큼 answer에 더해준다. table 블록 좌표 개수와 board 빈공간 좌표 개수가 맞지않으면 아예 크기부터가 다른 도형이기 때문에 넘어가고, 또한 이미 사용된 도형인 경우에도 체크하지 않고 넘어간다.

 

도형을 회전시키는 방법은 간단하다. 도형을 90도 회전시키기 위해서는 모든 좌표에 대해 (x, y) -> (y, -x)로 변경해주면 된다.

 

이제 회전시키며 빈공간과 도형을 비교하면 된다. 이때, 빈공간과 도형 모두 오름차순으로 정렬하여 비교하도록 한다. 빈 공간과 도형 모두 블록 내 같은 위치에서 비교되야 하기 때문이다.

 

코드

import java.util.*;
class Solution {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static List<List<Node>> matrixBList;
    static List<List<Node>> matrixTList;
    static int size;
    static int answer;
    
    public int solution(int[][] game_board, int[][] table) {
        answer = 0;
        size = game_board.length;
        boolean[][] visitedB = new boolean[size][size];
        boolean[][] visitedT = new boolean[size][size];
        
        matrixTList = new ArrayList<>();
        matrixBList = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (visitedB[i][j] == false && game_board[i][j] == 0) {
                    System.out.println("방문 x, y = " + i +" "+ j);
                    bfs(game_board, i, j, 0, visitedB, matrixBList);
                }
                if (visitedT[i][j] == false && table[i][j] == 1) {
                    bfs(table, i, j, 1, visitedT, matrixTList);
                }
            }
        }
        compare(matrixBList, matrixTList);
        
        return answer;
    }
    
    public void bfs(int[][] board, int x, int y, int flag, boolean[][] visited, List<List<Node>> matrix) {
        
        visited[x][y] = true;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        
        List<Node> list = new ArrayList<>();
        list.add(new Node(0, 0));
        
        while (!q.isEmpty()) {
            Node n = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (isRange(nx, ny) && board[nx][ny] == flag && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new Node(nx, ny));
                    list.add(new Node(nx - x, ny - y));
                }
            }
        }
        matrix.add(list);
    }
    
    
    
    public void compare(List<List<Node>> matrixBList, List<List<Node>> matrixTList){
        boolean[] visited = new boolean[matrixTList.size()];
        
        for (int i = 0; i < matrixBList.size(); i++) {
            for (int j = 0; j < matrixTList.size(); j++) {
                if (visited[j] || matrixBList.get(i).size() != matrixTList.get(j).size()) {
                    continue;
                }
                if (!visited[j] && isAble(matrixBList.get(i), matrixTList.get(j))) {
                    visited[j] = true;
                    answer += matrixBList.get(i).size();
                    break;
                }
            }
        }
    }
    
    public boolean isAble(List<Node> board, List<Node> table) {
        Collections.sort(board);
        for (int i = 0; i < 4; i++) {
            //오름차순 정렬. table은 회전할때마다 다시 정렬해줌.
            Collections.sort(table);
            
            int curr_x = table.get(0).x;
            int curr_y = table.get(0).y;
            
            //회전하면서 좌표가 바뀌기 때문에, 다시 (0,0) 기준으로 세팅
            for(int j=0; j<table.size(); j++){
                table.get(j).x -= curr_x;
                table.get(j).y -= curr_y;
            }
            
            boolean check = true;
            for(int j=0; j<board.size(); j++){
                if(board.get(j).x != table.get(j).x || board.get(j).y != table.get(j).y){
                    check = false;
                    break;
                }
            }
            if (check) 
                return true;
            else {
                 for(int j=0; j<table.size(); j++){
                    int temp = table.get(j).x;
                    table.get(j).x = table.get(j).y;
                    table.get(j).y = -temp;
                }
            }
        }
        return false;
    }
    
    
    public boolean isRange(int x, int y) {
        return x >= 0 && x < size && y >= 0 && y < size;
    }
    
    
    class Node implements Comparable<Node>{
        int x, y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        @Override
        public int compareTo(Node o){
            int res = Integer.compare(this.x, o.x);
            if(res==0){
                res = Integer.compare(this.y, o.y);
            }
            return res;
        }
    }
}