import java.util.*;
class Solution {
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
List<int[][]> boardList = new ArrayList<>();
List<int[][]> tableList = new ArrayList<>();
// game_board에서 빈 공간(0)을 조각으로 추출하여 boardList에 저장
saveList(game_board, boardList, 0);
// table에서 채워진 공간(1)을 조각으로 추출하여 tableList에 저장
saveList(table, tableList, 1);
// 각 테이블 조각을 게임 보드의 빈 공간과 비교하여 맞는지 확인
boolean[] used = new boolean[tableList.size()];
for (int[][] boardPiece : boardList) {
for (int i = 0; i < tableList.size(); i++) {
if (!used[i] && doesPieceMatch(boardPiece, tableList.get(i))) {
answer += countCells(tableList.get(i)); // 맞으면 셀 개수 더함
used[i] = true;
break;
}
}
}
return answer;
}
// 빈 공간 또는 채워진 공간을 찾아서 조각 리스트에 저장
public static void saveList(int[][] board, List<int[][]> result, int targetNum) {
int n = board.length;
boolean[][] visited = new boolean[n][n]; // 방문 여부 체크를 위한 배열
// 상, 하, 좌, 우 탐색을 위한 방향 배열
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 보드 전체를 순회하며 DFS로 조각을 찾음
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 아직 방문하지 않은 targetNum인 경우 DFS 시작
if (board[i][j] == targetNum && !visited[i][j]) {
List<int[]> piece = new ArrayList<>(); // 현재 조각을 저장할 리스트
dfs(board, visited, i, j, piece, targetNum, dx, dy);
// 조각을 배열로 변환하여 result에 추가
result.add(convertPieceToArray(piece));
}
}
}
}
// DFS 탐색 함수
private static void dfs(int[][] board, boolean[][] visited, int x, int y, List<int[]> piece, int targetNum, int[] dx, int[] dy) {
visited[x][y] = true;
piece.add(new int[]{x, y});
int n = board.length;
// 상, 하, 좌, 우 방향으로 탐색
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위 내에 있고, 방문하지 않았으며, targetNum과 동일한 경우
if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == targetNum && !visited[nx][ny]) {
dfs(board, visited, nx, ny, piece, targetNum, dx, dy);
}
}
}
// 조각을 리스트에서 2차원 배열로 변환
private static int[][] convertPieceToArray(List<int[]> piece) {
// 조각의 크기를 구함
int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
for (int[] coord : piece) {
minX = Math.min(minX, coord[0]);
minY = Math.min(minY, coord[1]);
maxX = Math.max(maxX, coord[0]);
maxY = Math.max(maxY, coord[1]);
}
// 조각을 담을 배열 생성
int[][] array = new int[maxX - minX + 1][maxY - minY + 1];
// 조각의 좌표를 배열에 채움
for (int[] coord : piece) {
array[coord[0] - minX][coord[1] - minY] = 1;
}
return array;
}
// 조각을 회전시키는 함수
public static int[][] rotate(int[][] piece) {
int n = piece.length;
int m = piece[0].length;
int[][] rotated = new int[m][n]; // 회전된 조각을 저장할 배열
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
rotated[j][n - 1 - i] = piece[i][j]; // 시계 방향으로 90도 회전
}
}
return rotated;
}
// 두 조각이 같은지 비교하는 함수
public static boolean areSamePiece(int[][] piece1, int[][] piece2) {
if (piece1.length != piece2.length || piece1[0].length != piece2[0].length) {
return false; // 크기가 다르면 일치할 수 없음
}
for (int i = 0; i < piece1.length; i++) {
for (int j = 0; j < piece1[0].length; j++) {
if (piece1[i][j] != piece2[i][j]) {
return false; // 값이 다르면 일치하지 않음
}
}
}
return true;
}
// 테이블에서 가져온 조각이 게임 보드의 빈 공간과 일치하는지 확인
public static boolean doesPieceMatch(int[][] boardPiece, int[][] tablePiece) {
// 0도, 90도, 180도, 270도 회전해서 비교
for (int i = 0; i < 4; i++) {
if (areSamePiece(boardPiece, tablePiece)) {
return true; // 조각이 일치하면 true 반환
}
tablePiece = rotate(tablePiece); // 90도 회전
}
return false;
}
// 조각의 칸 개수를 세는 함수
public static int countCells(int[][] piece) {
int count = 0;
for (int[] row : piece) {
for (int cell : row) {
if (cell == 1) {
count++;
}
}
}
return count;
}
}