프로그래머스 위클리 챌린지 3주차 - 퍼즐 조각 채우기
84021 - 퍼즐 조각 채우기
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 3 ≤
game_board의 행 길이 ≤ 50 game_board의 각 열 길이 =game_board의 행 길이- 즉, 게임 보드는 정사각 격자 모양입니다.
game_board의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
- 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
table의 행 길이 =game_board의 행 길이table의 각 열 길이 =table의 행 길이- 즉, 테이블은
game_board와 같은 크기의 정사각 격자 모양입니다. table의 모든 원소는 0 또는 1입니다.- 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
- 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
- 즉, 테이블은
game_board에는 반드시 하나 이상의 빈칸이 있습니다.table에는 반드시 하나 이상의 블록이 놓여 있습니다.
입출력 예
| game_board | table | result |
|---|---|---|
| [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] | [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] | 14 |
| [[0,0,0],[1,1,0],[1,1,1]] | [[1,1,1],[1,0,0],[0,0,0]] | 0 |
풀이
문제에서 제시한 규칙들은 다음과 같다.
-
조각은 회전 가능 & 뒤집기 불가능
-
게임 보드에 빈 공간 없이 딱 맞는 퍼즐 조각만 넣을 수 있음
-
최대한 많은 조각을 넣었을 때의 채워진 게임 보드 칸을 구해야 함
가장 먼저 입력으로 주어지는 테이블 값에 초점을 두었다. 2차원 배열 값만 제공되므로 테이블을 먼저 순차 탐색하면서 각각의 고유한 조각들의 정보를 얻는 것이 필요하다고 생각했다.
두 번째로는 각각의 조각을 게임 보드 빈 공간에 채워 넣는 것인데, 게임 보드와 테이블 각각의 x, y 좌표를 이동하면서 단 한 공간이라도 채우지 못한다면(빈 공간이 있는 경우, 빈 공간이 없는 경우 또는 배열을 벗어난 경우) 해당 조각을 채워 넣을 수 없음, 그렇지 않다면 채워 넣을 수 있음 으로 판단하면 되겠다고 생각했다.
마지막으로 조각을 회전할 수 있다는 것인데, 이런 문제가 처음이라 바로 해답을 떠올리진 못했지만 방법을 생각해냈다.
int[] dx = {0, 1, 0, -1}; // x, 우, x, 좌
int[] dy = {-1, 0, 1, 0}; // 하, x, 상, x
for (int i = 0; i < 4; i++) {
// for loop를 돌면서 상 하 좌 우 탐색
}
위와 같은 dx dy 값을 통해 인접한 인덱스들을 탐색하게 되는데 이를 응용하면 회전된 조각들의 비교를 쉽게 할 수 있다.
예를 들어 아래와 같은 게임 보드, 테이블이 있다고 하자.
(A,B,C : 빈공간 , 조각의 위치 / 0: 빈 공간 X)
보드 / 테이블
A B / B C
0 C / A 0
해당 조각을 90도 회전한다면 보드의 빈 공간에 채워 넣을 수 있는데, 이를 위해서 테이블의 인덱스들을 모두 회전하는 것은 시간 복잡도에 영향을 주기 때문에 바람직하지 않다.
게임 보드의 좌표 bx, by 그리고 테이블의 좌표 tx, ty 가 있다고 할 때 테이블이 90도 회전되었다고 가정 한 후 각각의 좌표값들을 이동하면 된다.
보드와 테이블 모두 A -> B -> C 순서로 탐색하면 빈 공간에 채워 넣을 수 있음을 판단할 수 있으므로 보드가 오른쪽으로 이동할 때 테이블은 위로 이동하면 된다.
int[] dx = {0, 1, 0, -1}; // x, 우, x, 좌
int[] dy = {-1, 0, 1, 0}; // 하, x, 상, x
int rotate = 1; // 회전을 위한 rotate 값 (1 => 90도 회전)
for (int i = 0; i < 4; i++) {
int _bx = bx + dx[i]; // 다음에 이동할 보드 x
int _by = by + dy[i]; // 다음에 이동할 보드 y
int _tx = tx + dx[(i + rotate) % 4]; // 다음에 이동할 테이블 x
int _ty = ty + dy[(i + rotate) % 4]; // 다음에 이동할 테이블 y
}
위와 같이 회전을 위한 rotate 변수를 이용하면 보드와 테이블 값을 함께 탐색할 때 테이블이 회전된 것처럼 탐색이 가능하다.
이렇게 회전된 경우까지 고려하여 빈 공간에 조각들을 모두 채워 넣으면 문제에서 원하는 값을 얻을 수 있다.
코드를 제출했을 때 가장 오래 걸리는 테스트 케이스는 2000ms 가량 소요되었다.
문제에서 게임 보드와 테이블의 1, 0 이 반대되는 의미를 가지고 있어서 게임 보드의 0과 1을 서로 바꾸어 주는 로직을 추가했는데 이를 제거하면 조금 더 실행 시간을 단축시킬 수 있을 것 같다!
코드(Java)
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class Solution {
private static final int BOARD = 0;
private static final int TABLE = 1;
private static final int[] dx = {0, 1, 0, -1};
private static final int[] dy = {-1, 0, 1, 0};
private static boolean result;
private static List<int[]> posList;
private static List<int[]> blocks = new ArrayList<>();
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
doClassification(game_board, BOARD);
doClassification(table, TABLE);
for (int y = 0; y < game_board.length; y++) {
for (int x = 0; x < game_board.length; x++) {
if (game_board[y][x] != 0) {
for (Iterator<int[]> iter = blocks.iterator(); iter.hasNext();) {
int[] block = iter.next();
for (int r = 0; r < 4; r++) {
boolean[][] visit = new boolean[game_board.length][game_board.length];
result = true;
posList = new ArrayList<>();
compare(visit, game_board, table, game_board[y][x], table[block[1]][block[0]], x, y, block[0], block[1], r);
if (result) {
answer += posList.size();
for (int[] pos : posList) {
game_board[pos[1]][pos[0]] = 0;
table[pos[3]][pos[2]] = 0;
}
iter.remove();
}
}
}
}
}
}
return answer;
}
// 게임 보드 0, 1 값 스위칭
// 각각의 고유한 조각들 판별
private void doClassification(int[][] arr, int type) {
boolean[][] visit = new boolean[arr.length][arr.length];
int n = 1;
if (type == BOARD) {
for (int y = 0; y < arr.length; y++) {
for (int x = 0; x < arr.length; x++) {
arr[y][x] = (arr[y][x] == 1) ? 0 : 1;
}
}
} else if (type == TABLE) {
for (int y = 0; y < arr.length; y++) {
for (int x = 0; x < arr.length; x++) {
if (!visit[y][x] && arr[y][x] != 0) {
blocks.add(new int[]{x, y});
find(arr, x, y, n++, visit);
}
}
}
}
}
private void find(int[][] arr, int x, int y, int n, boolean[][] visit) {
if (visit[y][x] || arr[y][x] == 0) return;
arr[y][x] = n;
visit[y][x] = true;
for (int i = 0; i < 4; i++) {
int _y = y + dy[i];
int _x = x + dx[i];
if (_y >= 0 && _y < arr.length && _x >= 0 && _x < arr.length) {
find(arr, _x, _y, n, visit);
}
}
}
/**
* 회전하여 비교 (회전 X => +0)
* 1. 90도 회전 : 상,좌 / 하,우 / 좌,하 / 우,상 => +1
* 2. 180도 회전 : 상,하 / 하,상 / 좌,우 / 우,좌 => +2
* 3. 270도 회전 : 상,우 / 하,좌 / 좌,상 / 우,하 => +3
*/
private void compare(boolean[][] visit, int[][] board, int[][] table, int b_zone, int t_zone, int bx, int by, int tx, int ty, int rotate) {
if (board[by][bx] != b_zone || table[ty][tx] != t_zone) {
result = false;
return;
}
visit[ty][tx] = true;
posList.add(new int[]{bx, by, tx, ty});
for (int i = 0; i < 4; i++) {
int _by = by + dy[i];
int _bx = bx + dx[i];
int _ty = ty + dy[(i + rotate) % 4];
int _tx = tx + dx[(i + rotate) % 4];
if (_by >= 0 && _by < board.length && _bx >= 0 && _bx < board.length
&& ((_ty < 0 || _ty >= board.length) || (_tx < 0 || _tx >= board.length))) {
if (board[_by][_bx] == b_zone) {
result = false;
return;
}
} else if (_ty >= 0 && _ty < board.length && _tx >= 0 && _tx < board.length
&& ((_by < 0 || _by >= board.length) || (_bx < 0 || _bx >= board.length))) {
if (table[_ty][_tx] == t_zone) {
result = false;
return;
}
} else if (_by >= 0 && _by < board.length && _bx >= 0 && _bx < board.length
&& _ty >= 0 && _ty < board.length && _tx >= 0 && _tx < board.length) {
if ((board[_by][_bx] == b_zone || table[_ty][_tx] == t_zone) && !visit[_ty][_tx]) {
compare(visit, board, table, b_zone, t_zone, _bx, _by, _tx, _ty, rotate);
}
else if (board[_by][_bx] != b_zone && table[_ty][_tx] == t_zone) {
result = false;
return;
}
}
}
}
}
댓글남기기