문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/84021
문제
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
알고리즘: BFS, 구현
풀이
table에 퍼즐 조각을 규칙에 맞게 game_board에 채웠을 때 채운 칸수를 출력하는 문제다.
내가 구현한 방식은 이렇다.
game_board에서 blank_list를 BFS로 구한다.
table에서는 piece_list를 BFS로 구한다.
그리고 piece_list의 요소 piece를 회전시키면서 blank에 채울 수 있는지 확인한다. 채울 수 있다면 퍼즐을 구성하는 1x1 정사각형의 개수를 answer에 더해준다.
여기서 어떻게 회전할 것 인지, 그리고 어떻게 blank와 piece를 비교할 것인지가 이 문제에 핵심이다.
-
회전
회전은 시계 방향으로 90도 회전한다고 가정했다. 회전했을 때 좌푯값의 변화는 x -> (회전하기 전 y좌표) 와 y -> ((H-1) - 회전하기 전 x좌표)다. -
비교
비교는 좌표를 통일해야 한다. 그러기 위해서 정렬을 해준다. y값을 오름차순으로, y값이 같다면 x값을 오름차순으로 정렬했으면 0번째 요소의 x,y좌푯값을 모든 요소에 마이너스 해준다.
나는 위 작업을 표준화 작업이라고 불렀다.
ex) (3,3), (3,4)의 좌푯값을 가진 정렬된 퍼즐에 표준화하면 (0,0), (0,1)이 됨
표준화 작업을 거치면 같은 모양은 똑같은 같은 순서, 같은 값을 가지게 됨. 그러므로 단순하게 순차 비교로 채울 수 있는지, 없는지 알 수 있다.
소스 코드
import java.util.*;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
static final int[] dx = {-1, 0, 1, 0};
static final int[] dy = {0, -1, 0, 1};
static boolean[][] visited;
static boolean[] fill;
static int W,H;
static ArrayList<ArrayList<Point>> blank_list = new ArrayList<>();
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
H = game_board.length;
W = game_board[0].length;
visited = new boolean[H][W];
//game_board에서 빈공간 찾기
for(int i=0; i<game_board.length; i++) {
for(int j=0; j<game_board[i].length; j++) {
if(!visited[i][j] && game_board[i][j] == 0) {
blank_list.add(standardization(BFS(new Point(j, i), game_board, 0)));
}
}
}
visited = new boolean[H][W]; //초기화
fill = new boolean[blank_list.size()];
//테이블에서 퍼즐 조각 찾기
for(int i=0; i<table.length; i++) {
for(int j=0; j<table[i].length; j++) {
if(!visited[i][j] && table[i][j] == 1) {
answer += find_space(BFS(new Point(j, i), table, 1));
}
}
}
return answer;
}
static ArrayList<Point> BFS(Point start, int[][] board, int v) {
ArrayList<Point> piece = new ArrayList<>();
Queue<Point> que = new LinkedList<>();
piece.add(start);
que.add(start);
visited[start.y][start.x] = true;
while(que.size() != 0) {
Point n = que.poll();
for(int i=0; i<4; i++) {
int nx = n.x + dx[i];
int ny = n.y + dy[i];
if((0 <= nx && nx <= W-1) && (0 <= ny && ny <= H-1)) {
if(!visited[ny][nx] && board[ny][nx] == v) {
piece.add(new Point(nx, ny));
que.add(new Point(nx, ny));
visited[ny][nx] = true;
}
}
}
}
return piece;
}
static ArrayList<Point> standardization(ArrayList<Point> piece) {
ArrayList<Point> s_piece = new ArrayList<>();
ArrayList<Point> copy_piece = deep_copy(piece);
Collections.sort(copy_piece, (a, b) -> {
int diff_y = a.y - b.y;
if(diff_y < 0) return -1;
else if(diff_y > 0) return 1;
else if(diff_y == 0) {
int diff_x = a.x - b.x;
if(diff_x < 0) return -1;
else if(diff_x > 0) return 1;
}
return 0;
});
for(int i=0; i<copy_piece.size(); i++) {
s_piece.add(new Point(copy_piece.get(i).x - copy_piece.get(0).x, copy_piece.get(i).y - copy_piece.get(0).y));
}
return s_piece;
}
static int find_space(ArrayList<Point> piece) {
for(int i=0; i<4; i++) {
//회전하면서 맞는 blank가 있는지 확인
ArrayList<Point> s_piece = standardization(piece);
for(int j=0; j<blank_list.size(); j++) {
if(!fill[j] && blank_list.get(j).size() == s_piece.size()) {
boolean possible = true;
for(int k=0; k<blank_list.get(j).size(); k++) {
Point blank = blank_list.get(j).get(k);
if((blank.x != s_piece.get(k).x) || (blank.y != s_piece.get(k).y)) {
possible = false;
break;
}
}
if(possible) {
fill[j] = true;
return s_piece.size();
}
}
}
piece = rotation_piece(piece);
}
return 0;
}
static ArrayList<Point> rotation_piece(ArrayList<Point> piece) {
//90도 시계 방향으로 회전
//회전하면 -> x값은 H - 회전하기전 y값, y값은 회전하기전 x값
ArrayList<Point> r90_piece = new ArrayList<>();
for(int i=0; i<piece.size(); i++) r90_piece.add(new Point((H - 1) - piece.get(i).y, piece.get(i).x));
return r90_piece;
}
static ArrayList<Point> deep_copy(ArrayList<Point> list) {
ArrayList<Point> copy_list = new ArrayList<>();
for(int i=0; i<list.size(); i++) copy_list.add(new Point(list.get(i).x, list.get(i).y));
return copy_list;
}
}