문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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 |
입출력 예 설명
입출력 예 #1
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
풀이 방법 생각
이 문제를 보고 어떻게 접근해야 할지 생각이 들지 않았다. 그래서 일단 어떻게 도형을 모양을 나타낼 것인지 생각했는데 도형 한 곳에서 시작해서 모든 곳을 채울 때까지 상하좌우 움직임을 통해 나타내야겠다고 생각했다. 너비 우선 탐색? 탐색을 통해 모든 곳을 채우도록 했고 채우는 경로로 도형을 표한하게 되었다. 그 후 도형마다 회전할 경우를 생각해야 하는데 table 전체를 돌린 후 다시 탐색하는 것을 통해 회전할 때 경로를 계산했다. 경로의 시작점을 (0,0) 지점부터 시작하기 때문에 돌리게 되면 시작점이 달라져 많게는 총 4가지 경우로 나오게 된다. 이제 도형을 game_board에 채워넣어야 하는데 넣기 위해서 table에서 한 도형의 경로를 계산할 때 그 도형이 game_board에 채워질 수 있는 도형일 경우 그 table에서 그 도형을 제외하고 game_borad에 채워가는 방법을 이용했다. 그렇게 4방향으로 회전하면서 반복을 통해 풀이했다.
내 코드
import java.util.ArrayList;
class Solution {
public int solution(int[][] game_board, int[][] table) {
int answer = 0;
ArrayList<String> list = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>();
ArrayList<String> list3 = new ArrayList<>();
int[][] clone_game_board = new int[game_board.length][game_board.length];
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table.length; j++) {
if (game_board[i][j] == 0) {
answer++;
}
if (table[i][j] == 1) {
table[i][j] = 0;
String str = "c";
aroundCheck(table, list, i, j, str, true);
list3.add(list.get(list.size() - 1));
}
}
}
cloneArray(game_board, clone_game_board);
for(int i = 0; i< 4; i++){
matchBlock(game_board, clone_game_board, list3, list2);
}
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table.length; j++) {
if (game_board[i][j] == 0) {
answer--;
}
}
}
return answer;
}
String aroundCheck(int[][] array, ArrayList<String> list, int i, int j, String str, boolean table) {
boolean ch = false;
int chk;
int reverseChk;
if (table) {
chk = 1;
reverseChk = 0;
} else {
chk = 0;
reverseChk = 1;
}
if (i - 1 >= 0 && array[i - 1][j] == chk) {
array[i - 1][j] = reverseChk;
str += "u";
ch = true;
str += aroundCheck(array, list, i - 1, j, str, table);
}
if (j + 1 < array.length && array[i][j + 1] == chk) {
array[i][j + 1] = reverseChk;
str += "r";
ch = true;
str += aroundCheck(array, list, i, j + 1, str, table);
}
if (i + 1 < array.length && array[i + 1][j] == chk) {
array[i + 1][j] = reverseChk;
str += "d";
ch = true;
str += aroundCheck(array, list, i + 1, j, str, table);
}
if (j - 1 >= 0 && array[i][j - 1] == chk) {
array[i][j - 1] = reverseChk;
str += "l";
ch = true;
str += aroundCheck(array, list, i, j - 1, str, table);
}
if (!ch) {
list.add(str);
}
return str;
}
void cloneArray(int[][] array1, int[][] array2) {
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1.length; j++) {
array2[i][j] = array1[i][j];
}
}
}
void rotateArray(int[][] array1, int[][] array2) {
int q = 0;
for (int i = 0; i < array1.length; i++, q++) {
int k = array1.length - 1;
for (int j = 0; j < array1.length; j++, k--) {
array2[i][j] = array1[k][q];
}
}
}
void matchBlock(int[][] game_board, int[][] clone_game_board, ArrayList<String> list, ArrayList<String> list2) {
for (int i = 0; i < game_board.length; i++) {
for (int j = 0; j < game_board.length; j++) {
if (game_board[i][j] == 0) {
clone_game_board[i][j] = 1;
String str = "c";
aroundCheck(clone_game_board, list2, i, j, str, false);
if (list.contains(list2.get(list2.size() - 1))) {
list.remove(list2.get(list2.size() - 1));
list2.remove(list2.size() - 1);
cloneArray(clone_game_board, game_board);
} else {
cloneArray(game_board, clone_game_board);
}
}
}
}
rotateArray(game_board, clone_game_board);
cloneArray(clone_game_board, game_board);
}
}
다른 사람 풀이
import java.util.*;
class Solution {
public class Node {
int x, y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public ArrayList<String> emptyList = new ArrayList<>();
public int N;
public int[] dx = {0, 0, -1, 1};
public int[] dy = {-1, 1, 0, 0};
public int solution(int[][] game_board, int[][] table) {
N = game_board.length;
int answer = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N ; j++) {
if(game_board[i][j] == 0) {
emptyList.add(bfs(game_board, i, j, 0));
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N ; j++) {
if(table[i][j] == 1) {
answer += find(bfs(table, i, j, 1));
}
}
}
return answer;
}
public int find(String s) {
// System.out.println("s : " + s);
int point = 0;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '1') point++;
}
for(int i = 0; i < emptyList.size(); i++) {
String str = emptyList.get(i);
for(int j = 0; j < 4; j++) {
str = rotate(str);
// System.out.println(str);
if(s.equals(str)) {
emptyList.remove(i);
return point;
}
}
}
return 0;
}
public String rotate(String s) {
String str = "";
int x = 0;
int y = 0;
for(int i = 0; i < s.length(); i++) {
if(x == 0) {
if(s.charAt(i) != ' ') {
y++;
}
}
if(s.charAt(i) == ' ') {
x++;
}
}
char[][] arr = new char[x][y];
StringTokenizer st = new StringTokenizer(s);
for(int i = 0; i < x; i++) {
arr[i] = st.nextToken().toCharArray();
}
for(int j = 0; j < y; j++) {
for(int i = x - 1; i >= 0; i--) {
str += arr[i][j];
}
str += " ";
}
return str;
}
public String bfs(int[][] arr, int i, int j, int mode) {
// mode 0 : game_board, mode 1 : table
String s = "";
ArrayDeque<Node> q = new ArrayDeque<>();
boolean[][] tmp = new boolean[N][N];
int x_min = i;
int x_max = i;
int y_min = j;
int y_max = j;
tmp[i][j] = true;
arr[i][j] = (mode + 1) % 2;
q.add(new Node(i, j));
while(!q.isEmpty()) {
Node cur = q.poll();
int x = cur.x;
int y = cur.y;
x_min = Math.min(x_min, x);
x_max = Math.max(x_max, x);
y_min = Math.min(y_min, y);
y_max = Math.max(y_max, y);
for(int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(!isBoundary(nx, ny)) continue;
if(arr[nx][ny] == mode) {
tmp[nx][ny] = true;
arr[nx][ny] = (mode + 1) % 2;
q.add(new Node(nx, ny));
}
}
}
for(int x = x_min; x <= x_max; x++) {
for(int y = y_min; y <= y_max; y++) {
s += tmp[x][y] ? "1" : "0";
}
s += " ";
}
return s;
}
public boolean isBoundary(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
}
너비 우선 탐색을 통해 비슷하게 구현한 것으로 보이나 코드가 훤씬 깔끔한 것 같다... (큰 차이는 아니지만 내 코드가 좀더 빠르게 나왔다.)
1과 0 그리고 빈칸을 통해 직접 game_board 도형의 모양을 구하고 그 모양을 직접 회전시키면서 table 도형과 매칭시켜주었다.
도형을 표현할 방법을 생각하지 못해서 경로를 통해 풀이했는데 이 풀이와 마찬가지로 여러 풀이들이 잘 풀이했다. 만약 옆에 있는 도형을 풀이한다면 "110 000 011" 이런 식으로 표현해서 풀이했다. 지금 생각해보면 쉬워보이는데 " " (빈칸)을 사용해서 다음 줄을 나타낸다는 것을 생각지도 못했다.
너비 우선 탐색을 할 때도 node 클래스를 만들고 queue를 이용해서 풀이했다.
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
| 복서 정렬하기 (0) | 2021.09.06 |
|---|---|
| 모음 사전 (0) | 2021.09.02 |
| 직업군 추천하기 (0) | 2021.08.23 |
| 상호 평가 (0) | 2021.08.10 |
| 메뉴 리뉴얼 (0) | 2021.08.08 |