[프로그래머스/자바] 퍼즐 조각 채우기 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 고득점 Kit의 DFS/BFS 문제다.

코드도 길고 구현이 빡셌지만 아이디어를 생각해내기까지 어렵지는 않았다.

 

 

 

        for (int i=0;i<N;i++) {
            for (int j=0;j<M;j++) {
                if (!visit_table[i][j] && table[i][j] == 1) bfs(table, i, j);
            }
        }

먼저 table에서 1로 채워진 배열들로 퍼즐 조각을 구성하는 배열들을 각각 만든다.

table 배열을 처음부터 탐색해 1인 원소를 시작 위치로 bfs를 호출한다.

이미 만들어진 퍼즐을 다시 만들면 안되기 때문에 visit로 방문 처리를 해준다.

 

0	1
1	1
0	1

0	0	1
0	1	1
0	0	1

이때 비어있는 행이나 열이 없게, 배열에 퍼즐이 꽉 채워지도록 한다.

(위 배열에서 첫 번째 배열은 퍼즐이 꽉 채워져 있음. 두 번째 배열은 0번째 열이 비어져 있음.)

 

        ArrayList<int[]> list = new ArrayList<>();
        
        list.add(new int[] {r, c});
        visit_table[r][c] = true;
        
        int maxR = r;
        int minR = r;
        int maxC = c;
        int minC = c;

배열의 크기를 정하기 위해서는 하나의 퍼즐에서 가장 작은 행/열, 가장 큰 행/열이 필요하다.

 

 

        int idx = 0;
        while (idx < list.size()) {
            int[] now = list.get(idx++);
            
            for (int i=0;i<4;i++) {
                int nextR = now[0] + move[i][0];
                int nextC = now[1] + move[i][1];
            
                if (!check(nextR, nextC) || visit_table[nextR][nextC] || table[nextR][nextC] == 0) continue;
                
                visit_table[nextR][nextC] = true;
                list.add(new int[] {nextR, nextC});
                    
                maxR = Math.max(maxR, nextR);
                minR = Math.min(minR, nextR);
                maxC = Math.max(maxC, nextC);
                minC = Math.min(minC, nextC);
            }
        }

시작 위치부터 상하좌우로 탐색하여 1인 원소의 위치를 ArrayList에 넣는다.

그러면 ArrayList 안에는 하나의 퍼즐을 이루는 원소의 위치가 저장되어 있을 것이다.

bfs에는 일반적으로 큐를 사용하지만, 배열을 만들기 위해 다시 원소들을 꺼내와야 하기 때문에 ArrayList를 사용했다.

꺼낼 인덱스와 ArrayList의 사이즈가 같아지면 while문을 빠져나온다.

 

 

    int[][] makeArr(ArrayList<int[]> list, int minR, int minC, int maxR, int maxC) {
        int n = maxR - minR + 1;
        int m = maxC - minC + 1;
        int[][] ret = new int[n][m];
        
        for (int[] loc : list) {
            ret[loc[0] - minR][loc[1] - minC] = 1;
        }
        
        return ret;
    }

bfs로 퍼즐 원소를 찾았으면, 그 원소들을 가지는 퍼즐 배열을 만든다.

퍼즐의 사이즈를 적절히 설정하고,

ArrayList에 담겨져 있는 원소의 위치를 1로 설정한다.

 

 

        for (int i=0;i<4;i++) {
            if (puzzle(arr, arr.length, arr[0].length)) {
                answer += list.size();
                break;
            }
            if (i != 3) arr = rotate(arr);
        }

puzzle() 함수를 통해 만들어진 퍼즐 원소를 game_baord에 채워넣는다.

채울 수 없다면 (puzzle()이 false를 반환하면) 퍼즐을 회전시키고 다시 반복한다.

회전하는 경우는 90, 180, 270만 가능하기 때문에 for문을 4번 반복한다. (첫 번째 for문은 회전시키지 않은 원소)

만약 채울 수 있다면 answer에 퍼즐 원소의 개수를 더하고 for문을 빠져나온다. 

 

 

 

 

전체 코드

import java.util.*;

class Solution {
    int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int N, M;
    int answer = 0;
    boolean[][] visit_table;
    boolean[][] visit_board;
    int[][] board;
    
    public int solution(int[][] game_board, int[][] table) {
        board = game_board;

        N = board.length;
        M = board[0].length;
        
        visit_table = new boolean[N][M];
        visit_board = new boolean[N][M];
        
        for (int i=0;i<N;i++) {
            for (int j=0;j<M;j++) {
                if (!visit_table[i][j] && table[i][j] == 1) bfs(table, i, j);
            }
        }
        
        return answer;
    }
    
    void bfs(int[][] table, int r, int c) {
        ArrayList<int[]> list = new ArrayList<>();
        
        list.add(new int[] {r, c});
        visit_table[r][c] = true;
        
        int maxR = r;
        int minR = r;
        int maxC = c;
        int minC = c;
        
        int idx = 0;
        while (idx < list.size()) {
            int[] now = list.get(idx++);
            
            for (int i=0;i<4;i++) {
                int nextR = now[0] + move[i][0];
                int nextC = now[1] + move[i][1];
            
                if (!check(nextR, nextC) || visit_table[nextR][nextC] || table[nextR][nextC] == 0) continue;
                
                visit_table[nextR][nextC] = true;
                list.add(new int[] {nextR, nextC});
                    
                maxR = Math.max(maxR, nextR);
                minR = Math.min(minR, nextR);
                maxC = Math.max(maxC, nextC);
                minC = Math.min(minC, nextC);
            }
        }
        
        int[][] arr = makeArr(list, minR, minC, maxR, maxC);
        for (int i=0;i<4;i++) {
            if (puzzle(arr, arr.length, arr[0].length)) {
                answer += list.size();
                break;
            }
            if (i != 3) arr = rotate(arr);
        }
        
    }
    
    int[][] makeArr(ArrayList<int[]> list, int minR, int minC, int maxR, int maxC) {
        int n = maxR - minR + 1;
        int m = maxC - minC + 1;
        int[][] ret = new int[n][m];
        
        for (int[] loc : list) {
            ret[loc[0] - minR][loc[1] - minC] = 1;
        }
        
        return ret;
    }
    
    boolean check(int r, int c) {
        if (r < 0 || r >= N || c < 0 || c >= M) return false;
        return true;
    }
        
    boolean puzzle(int[][] arr, int n, int m) {
        for (int i=0;i<N-n+1;i++) {
            Loop: for (int j=0;j<M-m+1;j++) {
                for (int k=0;k<n;k++) {
                    for (int l=0;l<m;l++) {
                        if (arr[k][l] == 1 && (board[i + k][j + l] == 1 || visit_board[i + k][j + l])) continue Loop;
                    }
                }
                if (checkPuzzle(i, j, arr, n, m)) return true;
            }
        }
        
        return false;
    }
    
    boolean checkPuzzle(int startR, int startC, int[][] arr, int n, int m) {
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (arr[i][j] == 1) {
                    board[startR + i][startC + j] = 1;
                    visit_board[startR + i][startC + j] = true;
                }
            }
        }
        
        boolean flag = false;
        Loop: for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (arr[i][j] == 1) {
                    for (int k=0;k<4;k++) {
                        int r = startR + i + move[k][0];
                        int c = startC + j + move[k][1];
                        
                        if (!check(r, c)) continue;
                        if (board[r][c] == 0) {
                            flag = true;
                            break Loop;
                        }
                    }
                }
            }
        }
        
        if (flag) {
            for (int i=0;i<n;i++) {
                for (int j=0;j<m;j++) {
                    if (arr[i][j] == 1) {
                        board[startR + i][startC + j] = 0;
                        visit_board[startR + i][startC + j] = false;
                    }
                }
            }
            return false;
        }
        
        return true;
    }
    
    int[][] rotate(int[][] a) {
        int n = a.length;
        int m = a[0].length;
        
        int[][] ret = new int[m][n];
        
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                ret[j][n - i - 1] = a[i][j]; 
            }
        }
        
        return ret;
    }
}