1. 문제
설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
2. 풀이
2-1. 조건
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
2-2. 풀이
프로그래머스 위클리 3주차 문제였는데 난이도가 갑자기 확 올라갔습니다.
하지만 문제를 잘 읽고 어떻게 구현할지 계획을 세우고 하나씩 구현하면
충분히 풀 수 있는 문제니까 도전해봅시다.
(여담 - 전체 4등, js 1등으로 풀었는데 아무도 좋아요를 눌러주지 않아서 슬픕니다...)
일단 문제의 접근을 어떻게 해야 쉽게 풀 수 있을지 고민부터 해봅시다.
문제에서 정리한 2-1에 명시된 조건은 이렇습니다.
게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
그 의미는 재귀함수로 퍼즐을 채우는 모든 경우를 탐색할 필요 없이
빈 칸에 딱 들어맞는 퍼즐만 채워주면 된다는 겁니다.
휴, 이제 좀 풀어볼 만하군요. 이제 계획을 세워봅시다.
계획 1 - 테이블을 순회하면서 BFS로 빈 칸 조각과 퍼즐 조각을 만들어 각각 리스트에 담습니다.
제가 현실 세계의 복잡한 문제를 컴퓨터 데이터화 하기 위해 선택한 자료구조는
2차원 배열입니다.
퍼즐 조각을 2차원 배열로 만들어서 각각 리스트에 담습니다.
// 좌표들의 최솟값, 최댓값을 리턴
const getMinMaxCoordinates = (coordinates) => coordinates.reduce((m, [y, x]) => {
m[0] = Math.min(m[0], y);
m[1] = Math.min(m[1], x);
m[2] = Math.max(m[2], y);
m[3] = Math.max(m[3], x);
return m;
}, [SIZE, SIZE, 0, 0]);
// 조각 얻기
const getPiece = (y, x, board, targetNumber) => {
const pieceCoordinates = [[y, x]]; // 조각 좌표 리스트
q.push([y, x]);
board[y][x] = -1;
while (q.length) {
const [curY, curX] = q.shift();
for (const [my, mx] of moves) {
const ny = curY + my;
const nx = curX + mx;
if (ny < 0 || ny >= SIZE || nx < 0 || nx >= SIZE) continue;
if (board[ny][nx] != targetNumber) continue;
pieceCoordinates.push([ny, nx]);
q.push([ny, nx]);
board[ny][nx] = -1;
}
}
const [minY, minX, maxY, maxX] = getMinMaxCoordinates(pieceCoordinates); // 좌표들의 최솟값, 최댓값 얻기
const size = Math.max(maxY - minY, maxX - minX) + 1; // 2차원 배열 사이즈
const piece = getTwoDimensionArray(size); // 2차원 배열 선언
// 2차원 배열에 조각의 좌표를 박아주기, 이 때 (0, 0) 좌표에 딱 맞도록 박아줍니다.
pieceCoordinates.forEach(([y, x]) => piece[y - minY][x - minX] = 1);
return piece;
};
// 계획1 - 테이블을 순회하면서 BFS로 빈 칸 조각과 퍼즐 조각을 만들어 각각 리스트에 담습니다.
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
if (table[i][j] == 1) {
puzzlePieces.push(getPiece(i, j, table, 1));
}
if (game_board[i][j] == 0) {
blankPieces.push(getPiece(i, j, game_board, 0));
}
}
}
여기서 getPiece함수는 2차원 배열을 return하는데요.
2차원 배열은 이런 모양으로 만들어집니다.
예를 들어 조각이
이런 모양일 때
[
[1, 1, 1],
[0, 1, 0],
[0, 0, 0]
]이런 2차원 배열을 리턴합니다.
이로 인해 조각을 회전하거나, 빈 칸과 조각의 모양이 일치하는지 비교하기도 쉬워집니다.
계획 2 - 조각의 회전 구현하기
일단 2차원 배열을 시계 방향으로 회전하는 로직을 생각해봅시다.
예를 들어 2 x 2 배열을 회전시킬 때
(0, 0), (0, 1) -> (1, 0), (0, 0)
(1, 0), (1, 1) (1, 1), (0, 1)이런 식으로 좌표가 변하게 됩니다.
규칙을 살펴보면 좌표를 (y, x) i를 행, j를 열로 정의했을 때,
y = size - j - 1, x = i 의 규칙을 가지고 있습니다.
즉, y좌표는 끝에서부터 점점 작아지고 x좌표는 현재행(이전엔 열)에 대해 고정이 됩니다.
// 좌표들의 최솟값, 최댓값을 리턴
const getMinMaxCoordinates = (coordinates) => coordinates.reduce((m, [y, x]) => {
m[0] = Math.min(m[0], y);
m[1] = Math.min(m[1], x);
m[2] = Math.max(m[2], y);
m[3] = Math.max(m[3], x);
return m;
}, [SIZE, SIZE, 0, 0]);
// 조각을 시계 방향으로 90도 회전하기
const rotatePiece = (piece) => {
const size = piece.length; // 조각의 크기
const pieceCoordinates = []; // 회전된 조각의 좌표를 담을 리스트
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (piece[size- j - 1][i]) { // 조각이 있을 때
pieceCoordinates.push([i, j]); // 조각의 좌표 넣기
}
}
}
const newPiece = getTwoDimensionArray(size); // 2차원 배열 선언
const [minY, minX] = getMinMaxCoordinates(pieceCoordinates); // 좌표 최솟값 리턴
// 2차원 배열에 조각의 좌표를 박아주기, 이 때 (0, 0) 좌표에 딱 맞도록 박아줍니다.
pieceCoordinates.forEach(([y, x]) => newPiece[y - minY][x - minX] = 1);
return newPiece;
};여기서 주의할 점은
회전할 때 조각을 (0, 0)에 가깝게 붙여줘야 합니다.
아까 예시에서 조각을 90도 회전했을 때
이런 모양이 나오고
2차원 배열로 표현했을 때
// 회전 -> // (0, 0)에 가깝게 붙이기
[ [
[0, 0, 1], [0, 1, 0],
[0, 1, 1], [1, 1, 0],
[0, 0, 1] [0, 1, 0]
] ]
이런 2차원 배열을 리턴합니다.
(0, 0)에 붙어야 회전하고 나서 빈 칸과 딱 맞는지 비교할 수 있기 때문입니다.
계획 3 - 빈 칸 조각들에 퍼즐 조각들이 딱 들어맞는지 비교합니다.
이제 힘든 부분은 다 끝났습니다. 조금 더 힘을 냅시다.
// 해당 인덱스 번째의 빈 칸 조각이 덮였는지 여부
const isCoveredBlank = getOneDemensionArray(blankPieces.length);
// 정답 변수
let ans = 0;
for (let i = 0; i < puzzlePieces.length; i++) {
const puzzlePiece = puzzlePieces[i]; // 퍼즐 조각
const puzzleCellCount = getCellCount(puzzlePiece); // 퍼즐 조각의 셀 개수
for (let j = 0; j < blankPieces.length; j++) {
if (isCoveredBlank[j]) continue; // 이미 덮였으면 넘어갑니다.
let blankPiece = blankPieces[j]; // 빈 칸 조각
const size = blankPiece.length; // 빈 칸 조각 크기 (2차원 배열의 사이즈)
if (puzzlePiece.length != size) continue; // 사이즈가 다르면 넘어갑니다.
const blankCellCount = getCellCount(blankPiece); // 빈 칸 조각의 셀 개수
if (puzzleCellCount != blankCellCount) continue; // 셀 개수가 다르면 넘어갑니다.
let flag = false;
// 4회전 비교
for (let ro = 0; ro < 4; ro++) {
let isCorrect = true;
check:
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
// 한 부분이라도 틀릴 때 루프 아웃
if (puzzlePiece[i][j] != blankPiece[i][j]) {
isCorrect = false;
break check;
}
}
}
// 빈 칸 조각에 퍼즐 조각을 덮을 수 있을 때
if (isCorrect) {
flag = true;
break;
}
if (ro == 3) break;
// 빈 칸 조각 회전
blankPiece = rotatePiece(blankPiece);
}
if (!flag) continue;
// 해당 인덱스 번째의 빈 칸은 덮였다 표시
isCoveredBlank[j] = 1;
// 정답에 셀 개수 누적
ans += puzzleCellCount
// 루프 탈출
break;
}
}이런 식으로 비교해서 빈 칸 조각과 퍼즐 조각이 일치할 때만
셀 개수를 누적합니다.
3. 전체 코드
function solution(game_board, table) {
const SIZE = table.length;
const puzzlePieces = [];
const blankPieces = [];
const q = [];
const moves = [[-1, 0], [0, 1], [1, 0], [0, -1]];
const getOneDemensionArray = (size) => ([...Array(size)].map(() => 0));
const getTwoDimensionArray = (size) => ([...Array(size)].map(() => getOneDemensionArray(size)));
// 좌표들의 최솟값, 최댓값을 리턴
const getMinMaxCoordinates = (coordinates) => coordinates.reduce((m, [y, x]) => {
m[0] = Math.min(m[0], y);
m[1] = Math.min(m[1], x);
m[2] = Math.max(m[2], y);
m[3] = Math.max(m[3], x);
return m;
}, [SIZE, SIZE, 0, 0]);
// 계획 2 - 조각의 회전 구현하기
const rotatePiece = (piece) => {
const size = piece.length;
const pieceCoordinates = [];
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (piece[size- j - 1][i]) {
pieceCoordinates.push([i, j]);
}
}
}
const newPiece = getTwoDimensionArray(size);
const [minY, minX] = getMinMaxCoordinates(pieceCoordinates);
pieceCoordinates.forEach(([y, x]) => newPiece[y - minY][x - minX] = 1);
return newPiece;
};
// 조각 얻기
const getPiece = (y, x, board, targetNumber) => {
const pieceCoordinates = [[y, x]]; // 조각 좌표 리스트
q.push([y, x]);
board[y][x] = -1;
while (q.length) {
const [curY, curX] = q.shift();
for (const [my, mx] of moves) {
const ny = curY + my;
const nx = curX + mx;
if (ny < 0 || ny >= SIZE || nx < 0 || nx >= SIZE) continue;
if (board[ny][nx] != targetNumber) continue;
pieceCoordinates.push([ny, nx]);
q.push([ny, nx]);
board[ny][nx] = -1;
}
}
const [minY, minX, maxY, maxX] = getMinMaxCoordinates(pieceCoordinates); // 좌표들의 최솟값, 최댓값 얻기
const size = Math.max(maxY - minY, maxX - minX) + 1; // 2차원 배열 사이즈
const piece = getTwoDimensionArray(size); // 2차원 배열 선언
// 2차원 배열에 조각의 좌표를 박아주기, 이 때 (0, 0) 좌표에 딱 맞도록 박아줍니다.
pieceCoordinates.forEach(([y, x]) => piece[y - minY][x - minX] = 1);
return piece;
};
// 조각의 셀 개수 리턴
const getCellCount = (piece) => piece.reduce((m, row) => (
row.reduce((m, col) => m += col, m)
), 0);
// 계획 1 - 테이블을 순회하면서 BFS로 빈 칸 조각과 퍼즐 조각을 만들어 각각 리스트에 담습니다.
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
if (table[i][j] == 1) {
puzzlePieces.push(getPiece(i, j, table, 1));
}
if (game_board[i][j] == 0) {
blankPieces.push(getPiece(i, j, game_board, 0));
}
}
}
// 계획 3 - 빈 칸 조각들에 퍼즐 조각들이 딱 들어맞는지 비교합니다.
// 해당 인덱스 번째의 빈 칸 조각이 덮였는지 여부
const isCoveredBlank = getOneDemensionArray(blankPieces.length);
// 정답 변수
let ans = 0;
for (let i = 0; i < puzzlePieces.length; i++) {
const puzzlePiece = puzzlePieces[i]; // 퍼즐 조각
const puzzleCellCount = getCellCount(puzzlePiece); // 퍼즐 조각의 셀 개수
for (let j = 0; j < blankPieces.length; j++) {
if (isCoveredBlank[j]) continue; // 이미 덮였으면 넘어갑니다.
let blankPiece = blankPieces[j]; // 빈 칸 조각
const size = blankPiece.length; // 빈 칸 조각 크기 (2차원 배열의 사이즈)
if (puzzlePiece.length != size) continue; // 사이즈가 다르면 넘어갑니다.
const blankCellCount = getCellCount(blankPiece); // 빈 칸 조각의 셀 개수
if (puzzleCellCount != blankCellCount) continue; // 셀 개수가 다르면 넘어갑니다.
let flag = false;
// 4회전 비교
for (let ro = 0; ro < 4; ro++) {
let isCorrect = true;
check:
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
// 한 부분이라도 틀릴 때 루프 아웃
if (puzzlePiece[i][j] != blankPiece[i][j]) {
isCorrect = false;
break check;
}
}
}
// 빈 칸 조각에 퍼즐 조각을 덮을 수 있을 때
if (isCorrect) {
flag = true;
break;
}
if (ro == 3) break;
// 빈 칸 조각 회전
blankPiece = rotatePiece(blankPiece);
}
if (!flag) continue;
// 해당 인덱스 번째의 빈 칸은 덮였다 표시
isCoveredBlank[j] = 1;
// 정답에 셀 개수 누적
ans += puzzleCellCount
// 루프 탈출
break;
}
}
return ans;
}
함수형 프로그래밍, 자바스크립트에 관심이 많습니다.
와 이거 3주차꺼 빼고 다풀었는데.. 난이도 조절 실패한게 아닌가 싶기도 하구 ㅠㅠ
잠깐 보는걸로는 이해가 안되네요. 감사합니다