문제 정의
- 테이블과 게임 보드가 주어진다.
- 테이블에 놓인 블럭을 상하좌우로 회전하여 게임보드의 빈 공간을 채운다.
- 주의사항은 다음과 같다.
- 조각은 한 번에 하나씩 채워 넣음
- 조각을 반전시킬 수는 없음
- 게임 보드에 세로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 된다. 즉, 한 블럭을 새로운 공간에 끼워넣었을 때, 끼워넣은 그 블럭 상하좌우로 빈 공간이 있으면 안 된다.
- 예를 들면 다음과 같은 상황은 불가하다.
이런 상황이 올바른 상황이다.
- 위와 같은 식으로 블럭을 채울 때, 가능한 많은 블럭을 채웠을 때의 블럭 칸수를 리턴
문제 해결 접근
- 이 문제의 관건은 다음과 같다.
- 게임보드의 빈 공간의 위치 및 모양, 테이블의 블럭 위치 및 모양 파악
- 테이블의 블럭을 상하좌우로 회전해가면서 게임보드의 특정 빈 공간에 맞는지 확인하기
게임 보드와 테이블의 구성 파악하기
- 게임보드와 테이블의 구성을 파악하기 위해서, bfs 알고리즘을 사용한다.
- 게임보드와 테이블의 크기는 똑같기 때문에, 이중 for문을 사용해서 좌표를 일일이 탐색한다.
- 좌표를 탐색하다가 table[i][j] 가 1이고, visitedTable[i][j]가 false면 bfs를 호출하고, game_table[i][j] 가 0이고, visitedBoard[i][j]가 false일 때도, bfs를 호출한다.
- 게임보드의 빈 공간 찾기와 테이블의 블럭 찾기 알고리즘은 동일하기 때문에, 동일한 메서드를 사용하지만, 메서드의 파라미터로 이 둘을 구분하여 알고리즘의 세부 디테일을 조정한다.
- bfs 메서드의 파라미터로는
- 이중 for문을 돌면서 발견한 특정 좌표의 x값
- y값
- 게임보드나 테이블의 방문처리 배열
- 게임보드나 테이블 판
- 게임보드와 테이블의 구분자
- 빈 공간 정보들 or 블럭 정보들이 담긴 list
- bfs를 이용해서 도형의 모양을 알 수 있는 방법은, 바로 좌표를 이용하는 것이다.
- bfs가 호출될 때마다, int[] 형 리스트 tempList를 만들어서, 그 리스트에다 현재 발견된 빈 공간이나 블럭을 구성하는 좌표 정보들을 모두 저장한다.
- 게임보드나 테이블 둘다 인접한 빈 공간 or 블럭이 없기 때문에, bfs를 이용해서 상하좌우로 이동해서 탐색을 하다보면, 결국에는 tempList에는 현재 도형에 대한 모든 좌표들이 저장되게 된다.
- tempList에 좌표를 저장할 때는, 상대 좌표로 저장해야 나중에 다른 도형과의 비교가 수월하기 때문에, 도형의 제일 머리 부분의 좌표를 {0,0}으로 고정하고 좌표를 구성한다.
- 이렇게 tempList가 전부 구성되면, 이 tempList를, bfs 메서드의 마지막 파라미터의 list에 추가한다.
테이블의 블럭을 상하좌우로 회전해가면서 게임보드의 특정 빈 공간에 맞는지 확인하기
- 테이블의 블럭을 회전할 때는, 정렬이 필요하다.
- 왜냐하면 빈 공간과 블럭이 딱 들어맞는지를 확인하기 위해서는, 이 둘에 대한 순차 탐색을 이용해서, 모든 좌표가 서로 일치할 때, 빈 공간에 블럭이 들어맞는다는 것을 확인할 수 있다.
- 순차탐색을 하기 위해서는, 게임보드나 테이블이나 똑같은 기준에 의해 정렬되어 있어야 서로 비교를 할 수 있기 때문에 둘 다 정렬을 하는 것이다.
- 정렬만 하면 되는 것은 아니다. 만약에 테이블의 블럭을 회전하게 되면, 원래의 원점은 원점이 아니게 되기 때문에, 새로 원점을 지정해주는 과정이 필요하다.
- 이렇게 90도씩 회전을 하고, 모든 좌표를 서로 비교하는 과정에서, 만약 모든 좌표가 서로 일치한다면 true를 리턴하고, 하나라도 일치하지 않는다면 바로 다음 회전을 진행하는 식으로 블록이 특정 빈 공간과 맞는지 확인한다.
- 특정 빈 공간과 블럭이 들어맞는다면, 더 이상 블럭은 사용이 불가하기 때문에, 방문처리를 하고, 다른 블럭들은 이제 그 공간에 끼울 수 없기 때문에 break문을 통해 탈출하여 다음 빈 공간을 탐색한다.
코드
import java.util.*;
class Solution {
int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
public int solution(int[][] game_board, int[][] table) {
List<List<int[]>> empties = new ArrayList<>();
List<List<int[]>> blocks = new ArrayList<>();
boolean[][] visitedBoard = new boolean[game_board.length][game_board.length];
boolean[][] visitedTable = new boolean[table.length][table.length];
for(int i = 0 ;i<game_board.length;i++){
for(int j = 0;j<game_board.length;j++){
if(game_board[i][j]==0&&!visitedBoard[i][j]){
visitedBoard[i][j] = true;
bfs(0,i,j,game_board,visitedBoard,empties);
}
if(table[i][j]==1&&!visitedTable[i][j]){
visitedTable[i][j] = true;
bfs(1,i,j,table,visitedTable,blocks);
}
}
}
return fillBoard(blocks,empties);
}
public int fillBoard(List<List<int[]>>blocks, List<List<int[]>>empties){
int size = 0;
boolean[] visited = new boolean[blocks.size()];
for(int i = 0; i<empties.size();i++){
for(int j = 0;j<blocks.size();j++){
if(empties.get(i).size()==blocks.get(j).size()&&!visited[j]){
if(isRotate(empties.get(i),blocks.get(j))){
size += empties.get(i).size();
visited[j] = true;
break;
}
}
}
}
return size;
}
public void bfs(int check, int startX, int startY, int[][] map, boolean[][] visited, List<List<int[]>> list){
Queue<int[]> queue = new LinkedList<>();
List<int[]> tempList = new ArrayList<>();
queue.add(new int[]{startX,startY});
tempList.add(new int[]{0,0});
while(!queue.isEmpty()){
int[] curPos = queue.poll();
for(int i = 0; i<4;i++){
int nextX = curPos[0] + dir[i][0];
int nextY = curPos[1] + dir[i][1];
if(nextX<0||nextY<0||nextX>=map.length||nextY>=map.length)
continue;
if(map[nextX][nextY]==check&&!visited[nextX][nextY]){
tempList.add(new int[]{nextX-startX, nextY-startY});
queue.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
}
}
}
list.add(tempList);
}
boolean isRotate(List<int[]> table, List<int[]>board){
board.sort((o1,o2)->{
if(o1[0]==o2[0])
return o1[1] - o2[1];
return o1[0] - o2[0];
});
for(int i = 0;i<4;i++){
table.sort((o1,o2)->{
if(o1[0]==o2[0])
return o1[1] - o2[1];
return o1[0] - o2[0];
});
int centerX = table.get(0)[0];
int centerY = table.get(0)[1];
for(int j = 0;j<table.size();j++){
table.get(j)[0] -= centerX;
table.get(j)[1] -= centerY;
}
boolean isFit = true;
for(int j = 0;j<table.size();j++){
int[] curBoardPoint = board.get(j);
int[] curTablePoint = table.get(j);
if(curBoardPoint[0]!=curTablePoint[0]||curBoardPoint[1]!=curTablePoint[1]){
isFit = false;
break;
}
}
if(isFit)
return true;
for(int j = 0;j<table.size();j++){
int temp = table.get(j)[0];
table.get(j)[0] = table.get(j)[1];
table.get(j)[1] = -temp;
}
}
return false;
}
}느낀점
내가 지금까지 풀어본 코테 문제중에 제일 어려웠다. 처음부터 끝까지 다른 블로그를 찾아가면서 코드를 작성했다. 블럭을 상하좌우로 회전하는 로직도 처음 짜보았고, 좌표 리스트를 bfs를 이용해서 형성한 다음에, 그 좌표 리스트를 관리하는 리스트를 구현하는 것도 이번이 처음이었다. 이런 문제는 어렵긴 하지만 특징이 뚜렷하기 때문에, 이와 비슷한 다른 문제가 나오면 이번의 경험을 통해서 쉽게 구현할 수 있을 것 같다. bfs로 빈 공간과 블럭의 모양을 찾아내고, 그걸 이용해서 최종 정답을 도출해내는 유형은 이번이 처음이어서 더 어렵게 느껴졌던 것 같다. 매번 쉬운 문제만 풀어간다면 성장하지 못하기 때문에, 이번 기회를 통해서 한 단계 더 성장한 것 같아서 뿌듯하다.