[JAVA] 프로그래머스 LEVEL3 퍼즐 조각 채우기

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

프로그래머스

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 퍼즐 조각 채우기

 

난이도: LEVEL3

알고리즘 유형: BFS + 구현(배열 회전) 

 

풀이 설명 

문제의 조건

조각을 회전시킬 수 있다. 

조각을 뒤집을 수는 없다. (그나마 다행) ... 

 

회전은 조각이 4가지 경우로 분리 

하지만 회전까지 가능하면 회전 + 뒤집기 같이 경우의 수가 엄청 늘어난다. 

 

1. game_board BFS 

 

game_board에는 여러 빈칸이 있다.

해당 빈칸은 모양에 맞는 조각으로 채울 수 있는데 

 

각 조각을 BFS 탐색하는데 해당 칸이 빈칸이면 BFS를 시작한다.

물론 재방문을 막기 위해서 visited boolean 배열을 사용하고 

index 범위에 벗어나지 않기 위해 매번 이동 시 검증기로 검사한다. 

// 방문 배열 
 boolean [][] visited = new boolean [n][n];

// ArrayIndexOutOfBounds 검사기 
public static boolean check(int nx, int ny){
    if(0 <= nx && 0 <= ny && nx < n && ny < n) return true;
    return false;
}

 

나는 game_board를 BFS 하고 이중 ArrayList에 조각을 저장한다. 

ArrayList 한개가 1개의 조각 

static ArrayList<ArrayList<int[]>> list = new ArrayList<>();

 

나는 추후에 계산하기 편하기 위해서 좌표를 전부 저장하는 게 아닌 

가장 x가 작고 가장 y가 작은 좌표를 기준으로 다른 좌표들은 어느 좌표에 있는지

즉 기준점을 기준으로 얼마나 x,y가 멀리 있는지만 저장을 하였다. 기준점은 저장 x 

 

즉 하나의 리스트에 저장할 때 현재 좌표 x - 시작 x, 현재 좌표 y - 시작 y 이렇게 int [] 저장  

 public static void gameboard(int [][] gb){
    boolean [][] visited = new boolean [n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // 이미 방문 or 채워진 칸 skip
            if(visited[i][j] || gb[i][j] == 1) continue;
            ArrayList<int[]> temp = new ArrayList<>();
            visited[i][j] = true; // 방문 표시 
            q.add(new int []{i, j}); // 큐에 현재 좌표 삽입
            while(!q.isEmpty()){
                int [] cur = q.poll();
                for(int k = 0; k < 4; k++){
                    int nx = cur[0] + arx[k];
                    int ny = cur[1] + ary[k];
                    // 다음 이동 체크 
                    if(!check(nx, ny) || visited[nx][ny] || gb[nx][ny] == 1) continue;
                    visited[nx][ny] = true; // 방문 표시 
                    temp.add(new int [] {nx - i, ny - j});
                    q.add(new int [] {nx, ny}); // 큐에 추가 
                }
            }
            temp.sort(com); // 정렬 
            list.add(temp); // 리스트에 삽입 
        }
    }
}

 

2. table BFS 

table 배열에는 여러가지 조각이 있다. 

해당 조각들은 마찬가지로 BFS를 통해서 찾고 

조각의 가장 넓은 길이를 구하고 해당 길이를 기준으로 정사각형 배열을 만들고 

좌표 min ~ max 까지 넣어주었다.

1번 조각과 2번 조각을 저장할 때 배열의 크기는 3 * 3 이다. 

가장 큰 길이 3

 

이렇게 배열을 만들어서 저장하는 이유는 나중에 회전시킬 때 

좌우 길이가 다른 배열을 만들면 회전에 맞게 배열에 크기도 재정의 해야 하지만 

이렇게 최대 크기로 만들어 놓으면 회전하더라도 크기는 고정이기 때문에
머리가 덜 아프다? 

 

각 조각들을 큐에 넣는다. 

static Queue<int[][]> blocks = new LinkedList<>();

큐에 넣는 이유는 game_board 빈칸 후보들에서 해당 조각이 들어가지 못하면 추후에 다른 빈칸에서 재검증해야 하기 때문이다.

public static void block(int [][] table){
    boolean [][] visited = new boolean [n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // 이미 방문 or 빈칸 skip
            if(visited[i][j] || table[i][j] == 0) continue;
            visited[i][j] = true; // 방문 표시 
            q.add(new int []{i, j}); // 큐에 현재 좌표 삽입
            int max_x = i;
            int max_y = j;
            int min_x = i;
            int min_y = j;
            while(!q.isEmpty()){
                int [] cur = q.poll();
                for(int k = 0; k < 4; k++){
                    int nx = cur[0] + arx[k];
                    int ny = cur[1] + ary[k];
                    // 다음 이동 체크 
                    if(!check(nx, ny) || visited[nx][ny] || table[nx][ny] == 0) continue;
                    visited[nx][ny] = true; // 방문 표시 
                    q.add(new int [] {nx, ny}); // 큐에 추가 
                    max_x = Math.max(max_x, nx);
                    max_y = Math.max(max_y, ny);
                    min_x = Math.min(min_x, nx);
                    min_y = Math.min(min_y, ny);
                }
            }
            // 모양 찍어내기 
            int max = Math.max(max_x - min_x, max_y - min_y) + 1;
            int [][] output = new int [max][max];
            for(int k = min_x; k <= max_x; k++){
                for(int l = min_y; l <= max_y; l++){
                    output[k-min_x][l-min_y] = table[k][l];
                }
            }   
            blocks.add(output);
        }
    }
}

 

3. 게임시작 game_start() 메소드 

 

게임을 하는 메소드이다. 

미리 빈칸 후보들을 저장해둔 list를 for문으로 먼저 돌리고 

블락들의 사이즈만큼 for문을 돌린다. 

만약 game_logic() 메소드에서 return 값이 true 이면 break 통해서 해당 빈칸의 검증을 끝내고 

만약 false면 다음 조각을 통한 검증을 한다.

추후에 다른 빈칸에서 해당 조각이 들어갈 수도 있으니 다시 큐에 넣어준다. 

public static void game_start(){
    for(ArrayList<int[]> cur : list){ // game_board 빈칸들 
        int size = blocks.size();
        for(int i = 0; i < size; i++){
            int [][] block = blocks.poll();   // 블록 꺼내기 
            if(game_logic(cur, block)) break; // 이번 블록으로 채웠다면 stop
            blocks.add(block);
        }
    }
}

 

4. game_logic() 메소드  

 

game_start() 메소드에서 빈칸 후보 ArrayList<int[]> 리스트와 이번에 검증할 block을 받아온다.

block에게 주어진 기회는 총 4번이다.

 

처음 count가 0이면 회전을 하지 않고 그대로 검사하고 

count 1이면 회전을 1번 count 2 회전을 2번 ...

4번을 하면 다시 처음 회전하지 않았던 상태로 돌아오기 때문에 stop 

 

처음 block 크기를 검사했을 때 이번 빈칸의 크기와 맞지 않으면 바로 return false 

더 검증할 이유가 없다. 

public static boolean game_logic(ArrayList<int[]> cur, int [][] block){
     int count = 0;
     int m = block.length; 
     while(count < 4){
         block = rotate(block, count); // 회전 시키기 
         boolean first = true;
         boolean end   = false;
         int size = 0;
         boolean [][] visited = new boolean [m][m];
         for(int i = 0; i < m; i++){
             for(int j = 0; j < m; j++){
                 if(block[i][j] == 0) continue;
                 ArrayList<int []> temp = new ArrayList<>();
                 visited[i][j] = true;
                 q.add(new int []{i, j});
                 while(!q.isEmpty()){
                     int [] out = q.poll();
                     for(int k = 0; k < 4; k++){
                         int nx = arx[k] + out[0];
                         int ny = ary[k] + out[1];
                         if(0 > nx || 0 > ny || nx >= m || ny >= m) continue;
                         if(visited[nx][ny] || block[nx][ny] == 0) continue;
                         visited[nx][ny] = true;
                         size++;
                         temp.add(new int [] {nx, ny});
                         q.add(new int [] {nx, ny});
                     }
                 }
                 if(temp.size() != cur.size()) return false; // 사이즈가 틀리면 바로 return
                 temp.sort(com); // 똑같은 방식으로 정렬 

                 boolean answer_check = true;
                 for(int k = 0; k < temp.size(); k++){
                     int [] board_get = cur.get(k);
                     int [] block_get = temp.get(k);
                     if(board_get[0] != block_get[0] - i || board_get[1] != block_get[1] - j){
                         answer_check = false;
                         break;
                     }
                 }
                 if(answer_check){
                     answer += cur.size() + 1;
                     return true;
                 }
                 first = false;
                 break;
             }
             if(!first) break;
         }
         count++;
     }
     return false;
}

 

5. 회전 메소드 

단순히 배열을 90도 회전 시키는 메소드이다. 

count = 0 즉 이번엔 회전을 하지 않는다면 바로 return 하고 

회전한다고 하면 새로운 배열에 회전값을 넣어서 return 해준다. 

public static int [][] rotate(int [][] block, int count){
    if(count == 0) return block;
    int m = block.length;
    int [][] change = new int [m][m];
    for(int i = 0; i < m; i++){
        for(int j = m - 1; j >= 0; j--){
            change[j][m - i - 1] = block[i][j];
        }
    }
    return change;
}

정답 코드 

import java.util.*;

class Solution {
    static int [] arx = {-1,1,0,0}; // 동서남북 BFS 탐색용 
    static int [] ary = {0,0,-1,1};
    static int n;
    static Queue<int[]> q = new LinkedList<>();
    // game_board 빈칸 모양들 저장 
    // 가장 왼쪽 위에 있는 좌표부터 하나씩 저장 
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    // table에 있었던 블록 모양 저장 
    static Queue<int[][]> blocks = new LinkedList<>();
    // x 오름차순 / y 오름차순 정렬 Comparator 
    static Comparator<int[]> com = (o1, o2) ->{
        if(o1[0] != o2[0]) return o1[0] - o2[0];
        return o1[1] - o2[1];
    };
    static int answer = 0; 
    public int solution(int[][] game_board, int[][] table) {
        n = game_board.length;
        gameboard(game_board);
        block(table);
        game_start();
        return answer;
    }
    public static void game_start(){
        for(ArrayList<int[]> cur : list){ // game_board 빈칸들 
            int size = blocks.size();
            for(int i = 0; i < size; i++){
                int [][] block = blocks.poll();   // 블록 꺼내기 
                if(game_logic(cur, block)) break; // 이번 블록으로 채웠다면 stop
                blocks.add(block);
            }
        }
    }
    public static boolean game_logic(ArrayList<int[]> cur, int [][] block){
         int count = 0;
         int m = block.length; 
         while(count < 4){
             block = rotate(block, count); // 회전 시키기 
             boolean first = true;
             boolean end   = false;
             int size = 0;
             boolean [][] visited = new boolean [m][m];
             for(int i = 0; i < m; i++){
                 for(int j = 0; j < m; j++){
                     if(block[i][j] == 0) continue;
                     ArrayList<int []> temp = new ArrayList<>();
                     visited[i][j] = true;
                     q.add(new int []{i, j});
                     while(!q.isEmpty()){
                         int [] out = q.poll();
                         for(int k = 0; k < 4; k++){
                             int nx = arx[k] + out[0];
                             int ny = ary[k] + out[1];
                             if(0 > nx || 0 > ny || nx >= m || ny >= m) continue;
                             if(visited[nx][ny] || block[nx][ny] == 0) continue;
                             visited[nx][ny] = true;
                             size++;
                             temp.add(new int [] {nx, ny});
                             q.add(new int [] {nx, ny});
                         }
                     }
                     if(temp.size() != cur.size()) return false; // 사이즈가 틀리면 바로 return
                     temp.sort(com); // 똑같은 방식으로 정렬 
                     
                     boolean answer_check = true;
                     for(int k = 0; k < temp.size(); k++){
                         int [] board_get = cur.get(k);
                         int [] block_get = temp.get(k);
                         if(board_get[0] != block_get[0] - i || board_get[1] != block_get[1] - j){
                             answer_check = false;
                             break;
                         }
                     }
                     if(answer_check){
                         answer += cur.size() + 1;
                         return true;
                     }
                     first = false;
                     break;
                 }
                 if(!first) break;
             }
             count++;
         }
         return false;
    }
    public static int [][] rotate(int [][] block, int count){
        if(count == 0) return block;
        int m = block.length;
        int [][] change = new int [m][m];
        for(int i = 0; i < m; i++){
            for(int j = m - 1; j >= 0; j--){
                change[j][m - i - 1] = block[i][j];
            }
        }
        return change;
    }
    public static void block(int [][] table){
        boolean [][] visited = new boolean [n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 이미 방문 or 빈칸 skip
                if(visited[i][j] || table[i][j] == 0) continue;
                visited[i][j] = true; // 방문 표시 
                q.add(new int []{i, j}); // 큐에 현재 좌표 삽입
                int max_x = i;
                int max_y = j;
                int min_x = i;
                int min_y = j;
                while(!q.isEmpty()){
                    int [] cur = q.poll();
                    for(int k = 0; k < 4; k++){
                        int nx = cur[0] + arx[k];
                        int ny = cur[1] + ary[k];
                        // 다음 이동 체크 
                        if(!check(nx, ny) || visited[nx][ny] || table[nx][ny] == 0) continue;
                        visited[nx][ny] = true; // 방문 표시 
                        q.add(new int [] {nx, ny}); // 큐에 추가 
                        max_x = Math.max(max_x, nx);
                        max_y = Math.max(max_y, ny);
                        min_x = Math.min(min_x, nx);
                        min_y = Math.min(min_y, ny);
                    }
                }
                // 모양 찍어내기 
                int max = Math.max(max_x - min_x, max_y - min_y) + 1;
                int [][] output = new int [max][max];
                for(int k = min_x; k <= max_x; k++){
                    for(int l = min_y; l <= max_y; l++){
                        output[k-min_x][l-min_y] = table[k][l];
                    }
                }   
                blocks.add(output);
            }
        }
    }
    public static void gameboard(int [][] gb){
        boolean [][] visited = new boolean [n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 이미 방문 or 채워진 칸 skip
                if(visited[i][j] || gb[i][j] == 1) continue;
                ArrayList<int[]> temp = new ArrayList<>();
                visited[i][j] = true; // 방문 표시 
                q.add(new int []{i, j}); // 큐에 현재 좌표 삽입
                while(!q.isEmpty()){
                    int [] cur = q.poll();
                    for(int k = 0; k < 4; k++){
                        int nx = cur[0] + arx[k];
                        int ny = cur[1] + ary[k];
                        // 다음 이동 체크 
                        if(!check(nx, ny) || visited[nx][ny] || gb[nx][ny] == 1) continue;
                        visited[nx][ny] = true; // 방문 표시 
                        temp.add(new int [] {nx - i, ny - j});
                        q.add(new int [] {nx, ny}); // 큐에 추가 
                    }
                }
                temp.sort(com); // 정렬 
                list.add(temp); // 리스트에 삽입 
            }
        }
    }
    // ArrayIndexOutOfBounds 검사기 
    public static boolean check(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < n && ny < n) return true;
        return false;
    }
}