오늘은 프로그래머스에서 깊이/너비 우선 탐색(DFS/BFS)의 마지막 문제로 퍼즐 조각 채우기 문제 풀이를 해보겠습니다. 드디어 깊이/너비 우선 탐색 문제도 마무리가 되어갑니다. 앞으로 남아있는 문제 세트는 3개이고, 문제는 7개입니다. 정말 프로그래머스 코딩테스트 고득점 Kit 문제 정복의 고지가 얼마 남지 않았습니다. 그럼 오늘의 문제인 퍼즐 조각 채우기 문제 풀이를 시작하도록 하겠습니다.
프로그래머스 > 깊이/너비 우선탐색(DFS/BFS) > 퍼즐 조각 채우기 문제 풀이
㏇ 문제 정보
문제명: 퍼즐 조각 채우기
문제 난이도: Level 3
문제 푼 사람 수: 1228명
사용 가능 언어: 11개 (JavaScript 사용)
㏇ 문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
º 조각은 한 번에 하나씩 채워 넣습니다. º조각을 회전시킬 수 있습니다. º조각을 뒤집을 수는 없습니다. º게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
º 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다. º 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
게임 보드에 테이블 위에 놓인 퍼즐 조각을 채워 넣을 수 있는 최대 칸 수 구하기
Inputs
game_board: 게임 보드의 상태 (빈 공간과 아닌 공간으로 구분 )
table: 테이블 위에 놓인 퍼즐 조각의 상태
Output: 규칙에 따라 최대한 많은 퍼즐 조각을 채워 넣을 경우의 최대 칸 수
㏇ 제한 사항
º 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
3 ≤ game_board의 행/열 길이, table의 행/열 길이 ≤ 50
game_board와 table은 정사각 격자 모양
game_board와 table의 원소는 0(빈칸), 1(이미 채워진 칸 or 조각이 놓인 칸)
1. table 위의 퍼즐 조각들을 좌표화된 정보를 목록으로 만든다. 2. game_board 위의 빈칸을 탐색한다. 2-1. 좌표화된 정보 만든 빈칸을 찾는다. 2-1-1. 퍼즐 조각의 회전한 모양까지 같은지 확인한다. 2-2. 같은 경우 퍼즐 조각을 제거하고 해당 크기만큼 결과에 더한다. 3. 모든 빈칸을 확인하였을 때의 결과를 반환한다.
퍼즐 조각 채우기 문제 풀이를 위한 알고리즘은 보기엔 짧아보이나 구현에서의 어려움이 있지 않을까하는 생각이 들게 되었습니다. 이번 문제가 Level 3이라는게 믿기지 않지만, 그래도 문제 풀이에서 포기하지 않고 풀어보도록 하겠습니다.
㏇ 코드 구현
function solution(game_board, table) {
const IS_EMPTY_IN_TABLE = 0;
const IS_BLOCK_IN_TABLE = 1;
const IS_EMPTY_IN_GAME_BOARD = 0;
const IS_FILLED_IN_GAME_BOARD = 1;
const DIRECTIONS = [[1, 0], [0, 1], [-1, 0], [0, -1]];
const N = table.length;
var answer = 0;
let blocks = [];
// 1. table 위의 퍼즐 조각들을 좌표화된 정보를 목록으로 만든다.
for(let x = 0; x < N; x++) {
for(let y = 0; y < N; y++) {
if(table[x][y] === IS_BLOCK_IN_TABLE) {
findBlock(x, y, table, IS_BLOCK_IN_TABLE, IS_EMPTY_IN_TABLE);
}
}
}
// 2. game_board 위의 빈칸을 탐색한다.
for(let x = 0; x < N; x++) {
for(let y = 0; y < N; y++) {
if(game_board[x][y] === IS_EMPTY_IN_GAME_BOARD) {
// 2-1. 좌표화된 정보 만든 빈칸을 찾는다.
const emptyShape = findShape(x, y, game_board, IS_EMPTY_IN_GAME_BOARD, IS_FILLED_IN_GAME_BOARD);
// 2-1-1. 퍼즐 조각의 회전한 모양까지 같은지 확인한다.
// 2-2. 같은 경우 퍼즐 조각을 제거하고 해당 크기만큼 결과에 더한다.
answer += checkBlock(emptyShape);
}
}
}
// 3. 모든 빈칸을 확인하였을 때의 결과를 반환한다.
return answer;
function findShape(x, y, board, load, visited) {
let block = [];
let queue = [[x, y]];
board[x][y] = visited;
while(queue.length > 0) {
const [curX, curY] = queue.shift();
block.push([curX, curY]);
for(let dir of DIRECTIONS) {
const [nextX, nextY] = [curX + dir[0], curY + dir[1]];
if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && board[nextX][nextY] === load) {
board[nextX][nextY] = visited;
queue.push([nextX, nextY]);
}
}
}
return blockInit(block);
}
function blockInit(block) {
block.sort((a, b) => (a[0] - b[0] === 0 ? a[1] - b[1] : a[0] - b[0]));
for(let i = 1; i < block.length; i++) {
block[i][0] -= block[0][0];
block[i][1] -= block[0][1];
}
block[0][0] = 0;
block[0][1] = 0;
return block;
}
function findBlock(x, y, board, shape, empty) {
blocks.push(findShape(x, y, board, shape, empty));
}
function checkBlock(shape) {
for(let n = 0; n < blocks.length; n++) {
if(blocks[n].length === shape.length) {
for(let i = 0; i < 4; i++) {
for(let j = 0; j < blocks[n].length; j++) {
blocks[n][j] = [blocks[n][j][1], -blocks[n][j][0]];
}
blocks[n] = blockInit(blocks[n]);
if(isSameBlock(shape, blocks[n])) {
blocks.splice(n, 1);
return shape.length;
}
}
}
}
return 0;
}
function isSameBlock(shape, block) {
let isSame = true;
for(let i = 0; i < shape.length; i++) {
if(shape[i][0] !== block[i][0] || shape[i][1] !== block[i][1]) {
isSame = false;
break;
}
}
return isSame;
}
}
역시 퍼즐 조각 채우기 문제는 알고리즘을 만들 때부터 구현에서의 어려움이 있을 것으로 생각했던 만큼, 길이가 길어졌습니다. 이에 모양을 찾거나, 블럭을 비교하는 등 이해할 수 있는 함수로 구분하여 구현하였습니다. 코드를 보는데 한결 편하리라 해봅니다.
㏇ 채점 결과
퍼즐 조각 채우기 문제 풀이 채점 결과 정확성 테스트 케이스 22개를 모두 통과하여 문제 풀이를 완료하였습니다.
이번 문제는 너비 우선 탐색(BFS)로 블럭들과 게임판의 빈칸을 계속 찾아가며 좌표로 된 객체들을 비교하고, 블럭을 회전하기도 하는 등 지금까지 풀었던 문제들보다 어려웠었다고 생각합니다. 하지만 이런 어려운 문제들도 풀어내며 한단계 발전하는 계기가 된 것 같아 뿌듯한 이번 퍼즐 조각 채우기 문제 풀이였습니다.
댓글