📖 오늘의 학습 키워드
BFS
오늘의 회고
문제
[퍼즐 조각 채우기]
https://school.programmers.co.kr/learn/courses/30/lessons/84021
나의 해결
import java.util.*;
class Solution {
public List<List<int[]>> gameBoard;
public List<List<int[]>> Table;
public boolean[][] visited;
public boolean[] visitedPuzzle;
public int len, answer;
public int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int solution(int[][] game_board, int[][] table) {
answer = 0;
len = game_board.length;
gameBoard = new ArrayList<>();
Table = new ArrayList<>();
visited = new boolean[len][len];
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
if(!visited[i][j] && table[i][j] == 1){
bfs(i, j, 1, table);
}
}
}
visited = new boolean[len][len];
for(int i = 0; i < len; i++) {
for(int j = 0; j < len; j++) {
if(!visited[i][j] && game_board[i][j] == 0){
bfs(i, j, 0, game_board);
}
}
}
visitedPuzzle = new boolean[Table.size()];
for(int i = 0; i < gameBoard.size(); i++) {
checkPuzzle(i);
}
return answer;
}
public void bfs(int i, int j, int target, int[][] board) {
Queue<int[]> q = new LinkedList<>();
List<int[]> temp = new ArrayList<>();
visited[i][j] = true;
q.offer(new int[]{i, j});
temp.add(new int[] {0, 0});
while(!q.isEmpty()){
int[] now = q.poll();
for(int[] d : directions){
int y = now[0] + d[0];
int x = now[1] + d[1];
if(x >= 0 && x < len && y >= 0 && y < len && board[y][x] == target && !visited[y][x]) {
q.offer(new int[]{y, x});
temp.add(new int[]{y-i, x-j});
visited[y][x] = true;
}
}
}
if(target == 0) {
gameBoard.add(temp);
}
else {
Table.add(temp);
}
}
public void checkPuzzle(int idx) {
List<int[]> board = gameBoard.get(idx);
for(int i = 0; i < Table.size(); i++) {
List<int[]> table = Table.get(i);
if(!visitedPuzzle[i] && table.size() == board.size()) {
if(isFit(board, table)){
answer += table.size();
visitedPuzzle[i] = true;
break;
}
}
}
}
public boolean isFit(List<int[]> board, List<int[]> table){
board.sort((a, b) -> {
if(a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
for(int i = 0; i < 4; i++) {
table.sort((a, b) -> {
if(a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
int startY = table.get(0)[0];
int startX = table.get(0)[1];
for(int j = 0; j < table.size(); j++) {
table.get(j)[0] -= startY;
table.get(j)[1] -= startX;
}
boolean fit = true;
for(int j = 0; j < table.size(); j++) {
int[] currTable = table.get(j);
int[] currBoard = board.get(j);
if(currTable[0] != currBoard[0] || currTable[1] != currBoard[1]) {
fit = false;
break;
}
}
if(!fit){
for(int j = 0; j < table.size(); j++) {
int temp = table.get(j)[0] * -1;
table.get(j)[0] = table.get(j)[1];
table.get(j)[1] = temp;
}
}
else {
return true;
}
}
return false;
}
}- BFS를 사용해서 게임보드에서의 빈 칸에 대한 정보와 테이블 위의 퍼즐 조각에 대한 정보(개수와 크기)를 저장한다.
- BFS를 이용해 각 빈칸과 퍼즐 조각를 구성하는 좌표값을 저장한다. BFS의 시작 격자의 좌표를 (0, 0)으로 간주하고 나머지 격자의 상대 좌표를 구해 저장한다.
- 게임보드 위 빈칸들 하나씩 각각의 퍼즐 조각과 대조하며 조각이 빈칸에 맞는지 확인하다.
- 중복 확인을 막기 위해 테이블 위 퍼즐 조각에 대한 방문 배열을 만든다.
- 빈칸을 구성하는 격자의 개수와 퍼즐 조각의 격자의 개수가 다르다면 굳이 비교하지 않다.
- 90, 180, 270도 회전하면서 해당 퍼즐이 빈칸에 맞는지 확인한다.
90도 시계방향 회전 : (y, x) -> (x, -y)
새로 학습한 내용
필요한 알고리즘을 떠올리는 데는 어렵지 않았으나 필요한 함수들을 구현하는 데 많은 시간이 필요했다. 코드를 작성하기 전에 필요한 함수와 변수들을 잘 정리해야겠다는 생각이 들었다. 그리고 좌표 회전 방법이 바로 떠오르지 않아 생각보다 여기서 시간을 많이 지체했다. 앞으로 이를 잘 기억해 두어야겠다.
