문제 출처
코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 퍼즐 조각 채우기
https://school.programmers.co.kr/learn/courses/30/lessons/84021
문제 설명
각각 2차원 배열 2개 퍼즐이 들어갈 공간 game_board, 퍼즐들의 위치 table 가 주어질 때, 최대한 많은 퍼즐을 game_board에 채워넣으면 총 몇칸을 넣을 수 있는 지 return 하라.
접근 방법
- game_board에서 퍼즐이 들어갈 공간(0), table에서 퍼즐 자체(1)를 찾는 과정 -> bfs
1-1. game_board에서는 퍼즐이 들어갈 수 있는 공간(0)을 찾는다. 해당 과정에서 (x,y) 시작 좌표의 상하좌우를 이용하여 공간의 크기를 파악하여 이를 subList에 저장하고 이를 boardList에 저장한다.
1-2. table에서는 퍼즐(1)을 찾는다. 해당 과정에서 (x,y) 시작 좌표의 상하좌우를 이용하여 공간의 크기를 파악하여 이를 subList에 저장하고 이를 tableList에 저장한다.
- bfs를 통해 차자낸 퍼즐 공간과 퍼즐을 하나씩 맞춰본다.
2-1. 퍼즐을 저장한 List tableList에서 퍼즐을 가져오고 해당 퍼즐과 boardList에서 하나씩 공간을 가져와 맞춰본다.
2-1-1. 맞춰보는 과정에서 일단 퍼즐의 사이즈를 비교하고, 그 공간이 사용되지 않았는지 확인한다.
2-1-2. 2-1-1 과정이 통과 되었으면, 해당 퍼즐을 90도씩 회전해가면서 들어갈 수 있나 확인하고, 만약 가능하다면 총 칸 수인 size를 계산한다.
라는 과정을 통해 총 칸수를 계산할 수 있다.
import java.util.*;
class Solution {
int[] dx = {-1, 0, 1 , 0}; // 상하좌우
int[] dy = {0, 1, 0, -1};
public int solution(int[][] game_board, int[][] table) {
boolean[][] visitedTable = new boolean[table.length][table.length];
boolean[][] visitedBoard = new boolean[game_board.length][game_board.length];
List<List<int[]>> boardList = new ArrayList<>();
List<List<int[]>> tableList = new ArrayList<>();
// game_board에서는 퍼즐이 들어갈 공간(0), table에서는 퍼즐 자체(1)를 찾는 과정
for (int i = 0; i < game_board.length; i++) {
for (int j = 0; j < game_board.length; j++) {
if (table[i][j] == 1 && !visitedTable[i][j]) {
bfs(i, j, visitedTable, table, 1, tableList); // 퍼즐 블록 찾아서 tableList에 저장
}
if (game_board[i][j] == 0 && !visitedBoard[i][j]) {
bfs(i, j, visitedBoard, game_board, 0, boardList); // 빈 공간 찾아서 boardList에 저장
}
}
}
// 이 전에 찾은 퍼즐 공간, 퍼즐을 조합하는 과정
return findBlock(boardList, tableList);
}
//퍼즐 공간과 퍼즐을 비교
public int findBlock(List<List<int[]>> board, List<List<int[]>> table) {
int size = 0;
int boardLen = board.size();
boolean[] visitedBoard = new boolean[boardLen];
for (List<int[]> tablePiece : table) {
for (int j = 0; j < boardLen; j++) {
List<int[]> boardSpace = board.get(j);
if (tablePiece.size() == boardSpace.size() && !visitedBoard[j]) { // 빈 공간 list에서 가져온 공간과 퍼즐의 size가 같고, 이미 맞춘 공간이 아니면 확인
if (isRotate(boardSpace, tablePiece)) {
size += tablePiece.size();
visitedBoard[j] = true;
break;
}
}
}
}
return size;
}
public boolean isRotate(List<int[]> board, List<int[]> table) {
boolean isMatched = false;
// 정렬 과정 -> 원래의 퍼즐 모양 형태를 유지하기 위함
// board의 x좌표를 비교하여 같으면 y좌표 비교 아닐경우 x좌표를 비교하여 정렬
board.sort((o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
for (int i = 0; i < 4; i++) { // 4회 회전하며 비교
// table의 x좌표를 비교하여 같으면 y좌표 비교 아닐경우 x좌표를 비교하여 정렬
table.sort((o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
// 기준점을 첫번째 퍼즐로 맞춤
int baseX = table.get(0)[0];
int baseY = table.get(0)[1];
for (int j = 0; j < table.size(); j++) { // 맨 처음 퍼즐도 (0,0)으로 기준이 맞춰지므로 이후엔 반복해도 영향 X
table.get(j)[0] -= baseX;
table.get(j)[1] -= baseY;
}
// 동일한지 확인
boolean isIdentical = true;
for (int j = 0; j < board.size(); j++) {
if (board.get(j)[0] != table.get(j)[0] || board.get(j)[1] != table.get(j)[1]) { //
isIdentical = false;
break;
}
}
if (isIdentical) {
isMatched = true;
break;
} else {
// 90도 회전
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 isMatched;
}
// 퍼즐 조각, 빈 공간 탐색
public void bfs(int currentX, int currentY, boolean[][] visited, int[][] graph, int blockOrEmpty, List<List<int[]>> list) {
// blockOrEmpty는 game_board의 경우 퍼즐을 넣을 수 있는 공간(빈 공간)이 0, table의 경우 퍼즐이 1로 표현
Queue<int[]> queue = new LinkedList<>();
visited[currentX][currentY] = true;
queue.add(new int[]{currentX, currentY});
List<int[]> subList = new ArrayList<>(); // 퍼즐 조각을 (0,0) 기준으로 정리하는 List
subList.add(new int[]{0, 0}); // 상대 좌표 기준 0,0
while (!queue.isEmpty()) {
int[] pop = queue.poll();
int popX = pop[0];
int popY = pop[1];
for (int i = 0; i < 4; i++) {
int nextX = popX + dx[i];
int nextY = popY + dy[i];
if (nextX < 0 || nextX >= graph.length || nextY < 0 || nextY >= graph.length) {
continue;
}
if (!visited[nextX][nextY] && graph[nextX][nextY] == blockOrEmpty) {
visited[nextX][nextY] = true;
queue.add(new int[]{nextX, nextY});
subList.add(new int[]{nextX - currentX, nextY - currentY}); // 상대좌표의 기준으로 current의 좌표로 잡았기 때문에 next-current
}
}
}
list.add(subList);
}
}Review
import java.util.*;
class Solution {
// 상하좌우
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
public int solution(int[][] game_board, int[][] table) {
// table, board의 방문 여부
boolean[][] visitedTable = new boolean[table.length][table.length];
boolean[][] visitedBoard = new boolean[game_board.length][game_board.length];
// board의 빈 공간, table의 퍼즐의 정보를 파악하기 위한 list
List<List<int[]>> boardList = new ArrayList<>();
List<List<int[]>> tableList = new ArrayList<>();
// game_board 퍼즐 공간(0) 확인, table의 퍼즐(1) 확인
for(int i = 0; i < game_board.length; i++){
for(int j = 0; j< game_board.length; j++){
if(table[i][j] == 1 && !visitedTable[i][j]){
bfs(i, j, visitedTable, table, 1, tableList);
}
if(game_board[i][j] == 0 && !visitedBoard[i][j]){
bfs(i, j, visitedBoard, game_board, 0, boardList);
}
}
}
return findBlock(boardList, tableList);
}
// 퍼즐 조각, 빈 공간 탐색
public void bfs(int currentX, int currentY, boolean[][] visited, int[][] graph, int blockOrEmpty, List<List<int[]>> list){
Queue<int[]> q = new LinkedList<>();
visited[currentX][currentY] = true;
q.add(new int[]{currentX, currentY});
List<int[]> subList = new ArrayList<>(); // 퍼즐 조각을 상대 좌표(0,0) 기준으로 정리하는 List
subList.add(new int[]{currentX - currentX, currentY - currentY}); // 상대 좌표의 기준은 (0,0)
while(!q.isEmpty()){
int[] point = q.poll();
int pointX = point[0];
int pointY = point[1];
for(int i = 0; i<4; i++){
int nX = pointX + dx[i];
int nY = pointY + dy[i];
if(nX < 0 || nX >= graph.length || nY < 0 || nY >= graph.length) continue;
if(!visited[nX][nY] && graph[nX][nY] == blockOrEmpty){
visited[nX][nY] = true;
q.add(new int[]{nX, nY});
subList.add(new int[]{nX - currentX, nY - currentY});
}
}
}
list.add(subList);
}
// 퍼즐 공간과 퍼즐을 비교(조합)
public int findBlock(List<List<int[]>> board, List<List<int[]>> table){
int size = 0;
int boardLen = board.size();
boolean[] visitedBoard = new boolean[boardLen];
for(List<int[]> tablePiece : table){
for(int j = 0; j < boardLen; j++){
List<int[]> boardSpace = board.get(j);
// 빈 공간과 퍼즐의 size가 맞고, 아직 퍼즐 공간이 채워진 곳이 아니라면
if(tablePiece.size() == boardSpace.size() && !visitedBoard[j]){
if (isRotate(boardSpace, tablePiece)){
size += tablePiece.size();
visitedBoard[j] = true;
break;
}
}
}
}
return size;
}
// 회전 가능 여부 확인
public boolean isRotate(List<int[]> board, List<int[]> table){
boolean isMatched = false;
board.sort((o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1],o2[1]) : Integer.compare(o1[0],o2[0]));
for (int i = 0; i < 4; i++){
table.sort((o1,o2) -> o1[0] == o2[0] ? Integer.compare(o1[1],o2[1]) : Integer.compare(o1[0],o2[0]));
// 기준점 -> 첫 번째 퍼즐
int baseX = table.get(0)[0];
int baseY = table.get(0)[1];
for (int j = 0; j< table.size(); j++){
// 상대 좌표로 바꾸는 과정
table.get(j)[0] -= baseX;
table.get(j)[1] -= baseY;
}
// 동일한지 확인
boolean isIdentical = true;
for (int j = 0; j < board.size(); j++) {
// 퍼즐의 좌표를 하나하나 확인해보면서 확인
if (board.get(j)[0] != table.get(j)[0] || board.get(j)[1] != table.get(j)[1]){
isIdentical = false;
break;
}
}
if(isIdentical){
isMatched = true;
break;
} else {
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 isMatched;
}
}알게된 점
해당 문제는 정말 생각할 것이 많다. 그 중 가장 크게 작용하는 것이, 퍼즐을 그대로 사용하는 것이 아니라, 상대 좌표로 맞추어 계산하는 것이다.
또한, 퍼즐과 퍼즐 공간은 좌표로 주어지므로 원래 형태를 유지하기 위해서 정렬을 사용해야한다.
해당 문제를 어떻게 풀지 이론적으로는 적어놓았지만, 거의 건드리지 못할 정도로 어려웠다.
내일 다시 풀어보면서 이해해봐야겠다.
출처
https://tmdrl5779.tistory.com/206
문제푼 흔적
Review
노력 해보려고 하는 사람(00년생 소프트웨어융합학과, 24년 12월 부터 백엔드 및 코테 공부 시작)