[프로그래머스] 퍼즐 조각 채우기 (Java, BFS, lv3)

문제 출처

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

프로그래머스

 

문제 풀이

 

요약 

1. game_board의 빈 영역(0)과 table의 블록 영역(1)을 구한다

2. 빈 영역에 블록이 끼워지는지 회전하며 최대 4번 비교한다

3. 블록이 빈 영역에 끼워질 경우 결과값에 블록 크기를 누적하고, 사용처리한다 (2-3 반복)

 

 

① game_board 의 빈 영역(0), table 에 블록 영역(1)을 BFS 로 구한다

List<List<int[]>> emptySpace = new ArrayList<>();
List<List<int[]>> blocks = new ArrayList<>();

int row = game_board.length;
int col = game_board[0].length;
boolean[][] visited = new boolean[row][col];
for(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
        if(game_board[i][j] == 0 && !visited[i][j]) {
            emptySpace.add(extractShape(i, j, row, col, game_board, visited, 0));
        }
    }
}

row = table.length;
col = table[0].length;
visited = new boolean[row][col];
for(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
        if(table[i][j] == 1 && !visited[i][j]) {
            blocks.add(extractShape(i, j, row, col, table, visited, 1));
        }
    }
}

 

 

extractShape는 정말 전형적인 BFS 풀이로 영역을 List<int[]> result에 담으면서 방문 처리를 한다

private static int[][] DIR = {
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0}
};

private List<int[]> extractShape(int startX, int startY, int row, int col, int[][] board, boolean[][] visited, int target) {
    List<int[]> result = new ArrayList<>();
    Deque<int[]> que = new ArrayDeque<>();
    que.add(new int[] {startX, startY});

    visited[startX][startY] = true;

    while(!que.isEmpty()) {
        int[] cur = que.poll();
        result.add(cur);

        for(int i = 0; i < 4; i++) {
            int dx = cur[0] + DIR[i][0];
            int dy = cur[1] + DIR[i][1];

            if(dx < 0 || dy < 0 || dx >= row || dy >= col) continue;
            if(visited[dx][dy]) continue;
            if(board[dx][dy] != target) continue;

            visited[dx][dy] = true;
            que.add(new int[] {dx, dy});
        }
    }

    return normalize(result);
}

 

 

이때 빈 영역과 블록 영역을 맞추는 것을 고려해서 정규화(normalize) 시킨 결과를 저장한다

- x의 최소치 , y의 최소치를 구해서 뺀다

private List<int[]> normalize(List<int[]> data) {
    if(data == null || data.isEmpty()) return data;

    int minX = Integer.MAX_VALUE;
    int minY = Integer.MAX_VALUE;

    for(int[] d : data) {
        minX = Math.min(minX, d[0]);
        minY = Math.min(minY, d[1]);
    }

    for(int[] d : data) {
        d[0] -= minX;
        d[1] -= minY;
    }

    return data;
}

 

 

 

 

② game_board의 빈 영역 (List<List<int[]>> emptySpace) 과 table의 블록 영역 (List<List<int[]>> blocks) 을 반복문 수행하며 매칭되는지 확인한다

 

코드는 심플하다.

- space 영역에 대해 사용하지 않은 block을 회전시키면서 끼워본다 

- space 영역에 끼워진다면 result에 블록 사이즈를 누적하고 boolean[] used에 블록 사용 처리를 해준다

private int match(List<List<int[]>> emptySpace, List<List<int[]>> blocks) {
    int result = 0;
    boolean[] used = new boolean[blocks.size()];

    for(int i = 0; i < emptySpace.size(); i++) {
        List<int[]> space = emptySpace.get(i); // 빈 공간

        for(int j = 0; j < blocks.size(); j++) {
            if(used[j]) continue; // 이미 사용한 블록인 경우 넘어간다

            List<int[]> block = blocks.get(j); // 블록
            if(rotateAndCompare(space, block)) {
                result += block.size(); // 블록 크기를 결과에 누적
                used[j] = true; // 사용처리
                break;
            }
        }
    }

    return result;
}

 

 

③ block 회전 시키고, 최소x, y와 좌표값에서 빼준다 (shift 처리)

회전 아이디어가 떠오르지 않았는데 chat - gpt가 친철하게 알려주었다 

 

- 절차1. (x, y) -> (y, -x) 로 이동 

- 절차2. 최소 x, y를 구해서 회전한 좌표에서 빼준다 (shift)

 

private boolean rotateAndCompare(List<int[]> space, List<int[]> block) {
    if(space.size() != block.size()) return false; // 사이즈가 틀린 경우

    List<int[]> rotated = block;
    for(int i = 0; i < 4; i++) { // 회전
        if(compare(space, rotated)) {
            return true; // 빈공간에 블록이 맞는 경우
        }

        if(i < 3) {
            rotated = rotate(rotated);
        }
    }

    return false; // 최종적으로 맞지 않는 경우
}

private List<int[]> rotate(List<int[]> block) {
    List<int[]> result = new ArrayList<>();
    int minX = Integer.MAX_VALUE;
    int minY = Integer.MAX_VALUE;
    for(int[] b : block) {
        int x = b[1];
        int y = -b[0];

        result.add(new int[] {x, y});

        if(x < minX) minX = x;
        if(y < minY) minY = y;
    }

    for(int[] r : result) {
        r[0] -= minX;
        r[1] -= minY;
    }

    return result;
}

 

 

 

④ space 영역과 rotate된 block 좌표를 정렬하여 동일한지 확인한다 

정렬 람다식을 해석하면 
(a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]

x좌표 a[0], b[0]이 같지 않으면 a[0] - b[0] x축 오름차순 정렬한다 
x좌표 a[0], b[0]이 같다면 a[1] - b[1] y축 기준 오름차순 정렬한다

 

private boolean compare(List<int[]> space, List<int[]> block) {
    Collections.sort(space, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // x가 같다면 y 오름차순
    Collections.sort(block, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

    for(int i = 0; i < space.size(); i++) {
        int[] s = space.get(i);
        int[] b = block.get(i);
        if(s[0] != b[0] || s[1] != b[1]) {
            return false;
        }
    }

    return true;
}

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int[][] game_board, int[][] table) {
        List<List<int[]>> emptySpace = new ArrayList<>();
        List<List<int[]>> blocks = new ArrayList<>();
        
        int row = game_board.length;
        int col = game_board[0].length;
        boolean[][] visited = new boolean[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(game_board[i][j] == 0 && !visited[i][j]) {
                    emptySpace.add(extractShape(i, j, row, col, game_board, visited, 0));
                }
            }
        }
        
        row = table.length;
        col = table[0].length;
        visited = new boolean[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(table[i][j] == 1 && !visited[i][j]) {
                    blocks.add(extractShape(i, j, row, col, table, visited, 1));
                }
            }
        }
        
        return match(emptySpace, blocks);
    }
    
    private static int[][] DIR = {
        {0, 1},
        {0, -1},
        {1, 0},
        {-1, 0}
    };
    
    private List<int[]> extractShape(int startX, int startY, int row, int col, int[][] board, boolean[][] visited, int target) {
        List<int[]> result = new ArrayList<>();
        Deque<int[]> que = new ArrayDeque<>();
        que.add(new int[] {startX, startY});
        
        visited[startX][startY] = true;
        
        while(!que.isEmpty()) {
            int[] cur = que.poll();
            result.add(cur);
            
            for(int i = 0; i < 4; i++) {
                int dx = cur[0] + DIR[i][0];
                int dy = cur[1] + DIR[i][1];
                
                if(dx < 0 || dy < 0 || dx >= row || dy >= col) continue;
                if(visited[dx][dy]) continue;
                if(board[dx][dy] != target) continue;
                
                visited[dx][dy] = true;
                que.add(new int[] {dx, dy});
            }
        }
        
        return normalize(result);
    }
    
    
    private List<int[]> normalize(List<int[]> data) {
        if(data == null || data.isEmpty()) return data;
        
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        
        for(int[] d : data) {
            minX = Math.min(minX, d[0]);
            minY = Math.min(minY, d[1]);
        }
        
        for(int[] d : data) {
            d[0] -= minX;
            d[1] -= minY;
        }
        
        return data;
    }
    
    private int match(List<List<int[]>> emptySpace, List<List<int[]>> blocks) {
        int result = 0;
        boolean[] used = new boolean[blocks.size()];
        
        for(int i = 0; i < emptySpace.size(); i++) {
            List<int[]> space = emptySpace.get(i); // 빈 공간
            
            for(int j = 0; j < blocks.size(); j++) {
                if(used[j]) continue;
                
                List<int[]> block = blocks.get(j); // 블록
                if(rotateAndCompare(space, block)) {
                    result += block.size();
                    used[j] = true;
                    break;
                }
            }
        }
        
        return result;
    }
    
    private boolean rotateAndCompare(List<int[]> space, List<int[]> block) {
        if(space.size() != block.size()) return false; // 사이즈가 틀린 경우
        
        List<int[]> rotated = block;
        for(int i = 0; i < 4; i++) { // 회전
            if(compare(space, rotated)) {
                return true;
            }
            
            if(i < 3) {
                rotated = rotate(rotated);
            }
        }
        
        return false;
    }
    
    private List<int[]> rotate(List<int[]> block) {
        List<int[]> result = new ArrayList<>();
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        for(int[] b : block) {
            int x = b[1];
            int y = -b[0];
            
            result.add(new int[] {x, y});
            
            if(x < minX) minX = x;
            if(y < minY) minY = y;
        }
        
        for(int[] r : result) {
            r[0] -= minX;
            r[1] -= minY;
        }
        
        return result;
    }
    
    
    private boolean compare(List<int[]> space, List<int[]> block) {
        Collections.sort(space, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); // x가 같다면 y 오름차순
        Collections.sort(block, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        
        for(int i = 0; i < space.size(); i++) {
            int[] s = space.get(i);
            int[] b = block.get(i);
            if(s[0] != b[0] || s[1] != b[1]) {
                return false;
            }
        }
        
        return true;
    }
}