https://school.programmers.co.kr/learn/courses/30/lessons/84021
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
프로그래머스 Lv3. 퍼즐 조각 채우기
작년에 풀다말았던 문제를 다시 풀어보았다.
왜 풀다 말았는지 알 것 같다.
요약하자면 table에 놓인 조각들을 game_board에 딱 맞게 최대한 많이 테트리스하면 되는 문제이다.
하지만 테트리스는 조각을 돌려가며 끼울 수 있다는 점~
어떻게 풀지?
불규칙한 조각들을 하나씩 돌리는 것 보단 고정된 game_board를 돌리는게 나아보인다.
퍼즐조각을 끼웠을 때, 인접한 칸이 비어있으면 안되므로 특정 조각이 들어갈 수 있는 칸은 정해져있다.
따라서 들어가기만 한다면, 최대 개수를 고려할 필요가 없다. 들어가기만 하면 ok!
따라서
- table에 놓인 퍼즐조각들을 bfs로 구분하여 저장한다.
- 조각들을 (0,0)기준으로 정규화하여 표현해둔다.
- game_board를 90도씩 돌려가며 bfs를 통해 빈공간을 찾는다.
- 빈공간 역시 (0,0) 기준으로 정규화하여 표현해둔다.
- 빈공간에 정규화된 퍼즐조각이 들어맞는지 확인한다.
직접 작성해보자.
- table에 놓인 퍼즐조각들을 bfs로 구분하여 저장한다 → 평범한 bfs 코드를 작성하면 된다.
private void bfs(int[][] board, int x, int y, int target, int mark, List<List<List<Integer>>> blocks) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
board[x][y] = mark;
List<List<Integer>> block = new ArrayList<>();
block.add(new ArrayList<>());
block.add(new ArrayList<>());
block.get(0).add(x);
block.get(1).add(y);
while(!queue.isEmpty()) {
int[] current = queue.poll();
int cX = current[0];
int cY = current[1];
for(int i = 0; i < 4; i++) {
int nX = cX + dx[i];
int nY = cY + dy[i];
if(nX < 0 || nY < 0 || nX >= size || nY >= size) continue;
if(board[nX][nY] == target) {
board[nX][nY] = mark;
queue.add(new int[]{nX, nY});
block.get(0).add(nX);
block.get(1).add(nY);
}
}
}
blocks.add(normalize(block));
}
조각들이 완성되면, normalize() 함수를 통해 정규화된 형태로 리스트에 추가한다.
private List<List<Integer>> normalize(List<List<Integer>> block) {
List<List<Integer>> normalized = new ArrayList<>();
normalized.add(new ArrayList<>());
normalized.add(new ArrayList<>());
// 최소 x, y 찾기
int minX = Collections.min(block.get(0));
int minY = Collections.min(block.get(1));
// 모든 좌표를 (0,0) 기준으로 이동
for(int i = 0; i < block.get(0).size(); i++) {
normalized.get(0).add(block.get(0).get(i) - minX);
normalized.get(1).add(block.get(1).get(i) - minY);
}
return normalized;
}
2. game_board의 빈공간을 찾는다
→ 퍼즐조각을 찾을 때와 동일하게 bfs를 돌려준다. 하지만 빈공간을 찾는거니까 mark 매개변수로 0과 1을 구분해준다.
3. 빈공간에 정규화된 퍼즐조각이 들어맞는지 확인한다.
public boolean isMatch(List<List<Integer>> board, List<List<Integer>> table) {
if(board.get(0).size() != table.get(0).size()) return false;
for(int r = 0; r < 4; r++) {
List<List<Integer>> rotated = rotate(table, r);
rotated = normalize(rotated);
// 좌표 정렬
List<String> boardPoints = new ArrayList<>();
List<String> tablePoints = new ArrayList<>();
for(int i = 0; i < board.get(0).size(); i++) {
boardPoints.add(board.get(0).get(i) + "," + board.get(1).get(i));
tablePoints.add(rotated.get(0).get(i) + "," + rotated.get(1).get(i));
}
Collections.sort(boardPoints);
Collections.sort(tablePoints);
if(boardPoints.equals(tablePoints)) return true;
}
return false;
}
- 블록의 크기 검사
- board를 90도씩 회전하면서 비교하기
- 회전된 블록을 다시 (0,0) 기준으로 정규화하고
- 좌표들을 정렬한 다음 일치하는지 비교하면
- 정렬된 좌표 리스트가 완전히 일치하면 들어맞는다고 판단한다.
최종 코드
import java.util.*;
class Solution {
int size = 0;
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, -1, 1};
List<List<List<Integer>>> tableBlocks;
List<List<List<Integer>>> boardBlocks;
boolean[] used;
public int solution(int[][] game_board, int[][] table) {
size = game_board.length;
tableBlocks = new ArrayList<>();
boardBlocks = new ArrayList<>();
int answer = 0;
// 게임 보드의 빈 공간 찾기
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
if(game_board[i][j] == 0) {
bfs(game_board, i, j, 0, 1, boardBlocks);
}
}
}
// 테이블의 블록 찾기
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
if(table[i][j] == 1) {
bfs(table, i, j, 1, 0, tableBlocks);
}
}
}
used = new boolean[tableBlocks.size()];
// 각 보드의 빈 공간에 대해 맞는 블록 찾기
for(List<List<Integer>> boardBlock : boardBlocks) {
for(int i = 0; i < tableBlocks.size(); i++) {
if(used[i]) continue;
List<List<Integer>> tableBlock = tableBlocks.get(i);
if(isMatch(boardBlock, tableBlock)) {
used[i] = true;
answer += boardBlock.get(0).size();
break;
}
}
}
return answer;
}
private List<List<Integer>> normalize(List<List<Integer>> block) {
List<List<Integer>> normalized = new ArrayList<>();
normalized.add(new ArrayList<>());
normalized.add(new ArrayList<>());
// 최소 x, y 찾기
int minX = Collections.min(block.get(0));
int minY = Collections.min(block.get(1));
// 모든 좌표를 (0,0) 기준으로 이동
for(int i = 0; i < block.get(0).size(); i++) {
normalized.get(0).add(block.get(0).get(i) - minX);
normalized.get(1).add(block.get(1).get(i) - minY);
}
return normalized;
}
private void bfs(int[][] board, int x, int y, int target, int mark, List<List<List<Integer>>> blocks) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
board[x][y] = mark;
List<List<Integer>> block = new ArrayList<>();
block.add(new ArrayList<>());
block.add(new ArrayList<>());
block.get(0).add(x);
block.get(1).add(y);
while(!queue.isEmpty()) {
int[] current = queue.poll();
int cX = current[0];
int cY = current[1];
for(int i = 0; i < 4; i++) {
int nX = cX + dx[i];
int nY = cY + dy[i];
if(nX < 0 || nY < 0 || nX >= size || nY >= size) continue;
if(board[nX][nY] == target) {
board[nX][nY] = mark;
queue.add(new int[]{nX, nY});
block.get(0).add(nX);
block.get(1).add(nY);
}
}
}
blocks.add(normalize(block));
}
public boolean isMatch(List<List<Integer>> board, List<List<Integer>> table) {
if(board.get(0).size() != table.get(0).size()) return false;
for(int r = 0; r < 4; r++) {
List<List<Integer>> rotated = rotate(table, r);
rotated = normalize(rotated);
// 좌표 정렬
List<String> boardPoints = new ArrayList<>();
List<String> tablePoints = new ArrayList<>();
for(int i = 0; i < board.get(0).size(); i++) {
boardPoints.add(board.get(0).get(i) + "," + board.get(1).get(i));
tablePoints.add(rotated.get(0).get(i) + "," + rotated.get(1).get(i));
}
Collections.sort(boardPoints);
Collections.sort(tablePoints);
if(boardPoints.equals(tablePoints)) return true;
}
return false;
}
public List<List<Integer>> rotate(List<List<Integer>> block, int rotateCount) {
List<List<Integer>> rotated = new ArrayList<>();
rotated.add(new ArrayList<>());
rotated.add(new ArrayList<>());
for(int i = 0; i < block.get(0).size(); i++) {
int x = block.get(0).get(i);
int y = block.get(1).get(i);
for(int r = 0; r < rotateCount; r++) {
int temp = x;
x = y;
y = -temp;
}
rotated.get(0).add(x);
rotated.get(1).add(y);
}
return rotated;
}
}
하나씩 뜯어보면 어려운건 없지만 풀다보면 화나서 끈기가 필요한 문제