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

 - 링크 : https://programmers.co.kr/learn/courses/30/lessons/84021?language=java 

코딩테스트 연습 - 3주차

 - 풀이

  : BFS + 구현 으로 해결

  : 보드 // 퍼즐 조각으로 구성 되어있는 배열들을 각각 빈 공간, 퍼즐 조각 공간을 가져 옴 (BFS)

  : 이후에 문제의 조건에 맞춰서 퍼즐 조각이 있는지 검색 후 있으면 count 를 더해 준다.

 

 

import java.util.*;

class Solution {
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    
    public int solution(int[][] game_board, int[][] table) {
        int answer = -1;
        int row = game_board.length;
        int col = game_board[0].length;
        List<List<Point>> board_pieces = new ArrayList<>();
        List<List<Point>> table_pieces = new ArrayList<>();
        
        for (int x=0; x<row; x++) {
            for (int y=0; y<col; y++) {
                if (game_board[x][y] == 0) {
                    List<Point> result = new ArrayList<>();
                    Queue<Point> q = new LinkedList<>();
                    q.add(new Point(x, y));
                    while(!q.isEmpty()) {
                        Point cp = q.poll();
                        int cx = cp.x;
                        int cy = cp.y;
                        if (game_board[cx][cy] == 1) {
                            continue;
                        }
                        game_board[cx][cy] = 1;
                        result.add(new Point(cx, cy));

                        for (int k=0; k<4; k++) {
                            int nx = cx + dx[k];
                            int ny = cy + dy[k];
                            if (isValid(nx, ny, row, col) && game_board[nx][ny] == 0) {
                                q.add(new Point(nx, ny));
                            }
                        }
                    }
                    board_pieces.add(result);
                }
            }
        }
        
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (table[i][j] == 1) {
                    List<Point> result = new ArrayList<>();
                    Queue<Point> q = new LinkedList<>();
                    q.add(new Point(i, j));
                    while(!q.isEmpty()) {
                        Point cp = q.poll();
                        int cx = cp.x;
                        int cy = cp.y;
                        if (table[cx][cy] == 0) {
                            continue;
                        }
                        table[cx][cy] = 0;
                        result.add(new Point(cx, cy));
                        
                        for (int k=0; k<4; k++) {
                            int nx = cx + dx[k];
                            int ny = cy + dy[k];
                            if (isValid(nx, ny, row, col) && table[nx][ny] == 1) {
                                q.add(new Point(nx, ny));
                            }
                        }
                    }
                    
                    table_pieces.add(result);
                }
            }
        }
        
        // 확인 시작
        int count = 0;
        board_pieces.sort((o1, o2) -> o1.size() - o2.size());
        table_pieces.sort((o1, o2) -> o1.size() - o2.size());
        for (List<Point> pieces : board_pieces) {
            if (isEqualPieces(table_pieces, pieces, row)) {
                count += pieces.size();
            };
        }
        return count;
    }
    
    public boolean isEqualPieces(List<List<Point>> table_pieces, List<Point> b_pieces, int n) {
        b_pieces.sort(Comparator.comparing(Point::getX).thenComparing(Comparator.comparing(Point::getY)));

        for (List<Point> t_pieces : table_pieces) {
            if (t_pieces.size() != b_pieces.size()) {
                continue;
            }
            
            for (int a=0; a<4; a++) {
                rotate(t_pieces, n);
                t_pieces.sort(Comparator.comparing(Point::getX).thenComparing(Comparator.comparing(Point::getY)));
                if (isEqualPiece(b_pieces, t_pieces)) {
                    table_pieces.remove(t_pieces);
                    return true;
                };
            }
        }
        
        return false;
    }
    
    public boolean isEqualPiece(List<Point> t_pieces, List<Point> b_pieces) {
            int diffX = t_pieces.get(0).x - b_pieces.get(0).x;
            int diffY = t_pieces.get(0).y - b_pieces.get(0).y;
            for (int i=1; i<t_pieces.size(); i++) {
                Point tp = t_pieces.get(i);
                Point bp = b_pieces.get(i);
                if (diffX != tp.x - bp.x || diffY != tp.y - bp.y) {
                    return false;
                }
            }
            return true;
    }
    
    public boolean isValid(int x, int y, int n, int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    
    public void rotate(List<Point> t_pieces, int n) {
        for (Point piece : t_pieces) {
            int rx = n - 1 - piece.y;
            int ry = piece.x;
            piece.setX(rx);
            piece.setY(ry);
        }
        
        return;
    }
}

class Point {
    int x;
    int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
    
    public void setX(int x) {
        this.x = x;
    }
    
    public void setY(int y) {
        this.y = y;
    }
}