[C++로 풀이] 블록 게임 ⭐⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 블록 게임
난이도 ⭐⭐⭐⭐
🚀 문제
🚀 내 풀이 ⭕
12 가지 블록들에 각각 번호를 붙여 정의한 상태
검은 블록은 위에서 떨어지기 때문에 검은 블록 2 개를 모두 받아 2 x 3 직사각형이 다 채워져 제거될 수 있는 블록은 3, 4, 6, 7, 9 번 블록이다. 그 외 블록은 절대 제거 될 수 없다.제거 될 수 있는 블록이라고 해서 항상 제거 될 수 있는 것은 아니다. 위 그림에서처럼 검은 블록이 놓여야 제거될 수 있는 자리의 윗 행들은 비어있어야 한다. 즉, 최종적으로 제거 가능한 블록 👉 3, 4, 6, 7, 9 번 블록이면서 검은 블록이 놓일 두 자리 위에는 비어있어야 함.
하나의 블록을 이루는 블록 내의 4개의 1x1 블록 중 1 번 이 시작점 기준으로 할 것이다. board를 이중 for문으로 순회하다보면 블록의 가장 처음으로 마주하게 되는 부분이기 떄문이다.
- 블록을 구별하는
board[i][j]값은value라고 부르겠다. - 위에서 내가 그림에서 정한 블록 종류를 나타내는 1 ~ 12 번호는
num혹은block이라고 부르겠다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
struct Pos { int i, j; };
struct Block { Pos pos1; Pos pos2; Pos pos3; Pos pos4; }; // 한 종류의 블록은 1x1 블록 4 개로 이루어져 있다.
int N = 0;
vector<vector<int>> Board; // board
unordered_map<int, bool> Checked; // Key : value (블록 board값), Value : 제거 가능 불가능 여부 판별 완료 된 블록이면 true 아니면 false
unordered_map<int, Pos> Start; // Key : value (블록 board값), Value : 해당 블록의 시작점
// 4 개의 위치가 모두 board 범위 안에 있는, 가능한 범위인지와 4 가지의 value 값이 다 같은지를 따져 가능한 블록인지를 판별하는 함수
bool PossiblePos(Block block, int value) {
if (block.pos1.i < 0 || block.pos1.j < 0 || block.pos1.i >= N || block.pos1.j >= N) return false;
if (block.pos2.i < 0 || block.pos2.j < 0 || block.pos2.i >= N || block.pos2.j >= N) return false;
if (block.pos3.i < 0 || block.pos3.j < 0 || block.pos3.i >= N || block.pos3.j >= N) return false;
if (block.pos4.i < 0 || block.pos4.j < 0 || block.pos4.i >= N || block.pos4.j >= N) return false;
if (Board[block.pos1.i][block.pos1.j] != value ||
Board[block.pos2.i][block.pos2.j] != value ||
Board[block.pos3.i][block.pos3.j] != value ||
Board[block.pos4.i][block.pos4.j] != value)
return false;
return true;
}
// pos1 위치를 시작점으로 하는 num 번 종류의 블록 내의 4 개 1x1 블록 리턴 {pos1, pos2, pos3, pos4}
Block BlockPos(Pos pos1, int num) {
if (num == 1) return { pos1, { pos1.i, pos1.j + 1 }, { pos1.i, pos1.j + 2 }, { pos1.i + 1, pos1.j + 2 } };
if (num == 2) return { pos1, { pos1.i, pos1.j + 1 }, { pos1.i + 1, pos1.j }, { pos1.i + 2, pos1.j } };
if (num == 3) return { pos1, { pos1.i + 1, pos1.j }, { pos1.i + 1, pos1.j + 1 }, { pos1.i + 1, pos1.j + 2 } };
if (num == 4) return { pos1, { pos1.i + 1, pos1.j }, { pos1.i + 2, pos1.j - 1 }, { pos1.i + 2, pos1.j } };
if (num == 5) return { pos1, { pos1.i, pos1.j + 1 }, { pos1.i, pos1.j + 2 }, { pos1.i + 1, pos1.j } };
if (num == 6) return { pos1, { pos1.i + 1, pos1.j }, { pos1.i + 2, pos1.j }, { pos1.i + 2, pos1.j + 1 } };
if (num == 7) return { pos1, { pos1.i + 1, pos1.j - 2 }, { pos1.i + 1, pos1.j - 1 }, { pos1.i + 1, pos1.j } };
if (num == 8) return { pos1, { pos1.i, pos1.j + 1 }, { pos1.i + 1, pos1.j + 1 }, { pos1.i + 2, pos1.j + 1 } };
if (num == 9) return { pos1, { pos1.i + 1, pos1.j - 1 }, { pos1.i + 1, pos1.j }, { pos1.i + 1, pos1.j + 1 } };
if (num == 10) return { pos1, { pos1.i + 1, pos1.j }, { pos1.i + 1, pos1.j + 1 }, { pos1.i + 2, pos1.j } };
if (num == 11) return { pos1, { pos1.i, pos1.j + 1 }, { pos1.i, pos1.j + 2 }, { pos1.i + 1, pos1.j + 1 } };
if (num == 12) return { pos1, { pos1.i + 1, pos1.j - 1 }, { pos1.i + 1, pos1.j }, { pos1.i + 2, pos1.j } };
}
// 시작점(pos1)와 블록의 value (board값)을 알면 어떤 블록 종류(num)인지를 알려주는 함수
int BlockName(Pos pos1, int value) {
Block block;
block = BlockPos(pos1, 1); if (PossiblePos(block, value)) return 1;
block = BlockPos(pos1, 2); if (PossiblePos(block, value)) return 2;
block = BlockPos(pos1, 3); if (PossiblePos(block, value)) return 3;
block = BlockPos(pos1, 4); if (PossiblePos(block, value)) return 4;
block = BlockPos(pos1, 5); if (PossiblePos(block, value)) return 5;
block = BlockPos(pos1, 6); if (PossiblePos(block, value)) return 6;
block = BlockPos(pos1, 7); if (PossiblePos(block, value)) return 7;
block = BlockPos(pos1, 8); if (PossiblePos(block, value)) return 8;
block = BlockPos(pos1, 9); if (PossiblePos(block, value)) return 9;
block = BlockPos(pos1, 10); if (PossiblePos(block, value)) return 10;
block = BlockPos(pos1, 11); if (PossiblePos(block, value)) return 11;
block = BlockPos(pos1, 12); if (PossiblePos(block, value)) return 12;
}
// 3, 4, 6, 7, 9 번 블록이면 지울 수 있는 가능성이 있는 블록
bool IsErasableBlock(int block) {
if (block == 3 || block == 4 || block == 6 || block == 7 || block == 9) return true;
else return false;
}
// 블록 종류(block)와 그 블록의 시작점 pos1 을 알려주면 검은 블록 2 개가 놓일 수 있는 자리를 벡터로 리턴해주는 함수
// 현재 그 자리가 다른 블록이 차지하고 있거나 한다면(즉, 검은 블록 놓일 수 있는 두 자리가 board 값이 0 이 아닌 상태) 검은 블록이 놓일 수 없는 상태이므로 벡터는 비어있는채로 리턴될 것
vector<Pos> BlackBlock(Pos pos1, int block) {
vector<Pos> blackblocks;
if (block == 3) {
Pos black1{ pos1.i, pos1.j + 1 }; Pos black2{ pos1.i, pos1.j + 2 };
if (Board[black1.i][black1.j] == 0 && Board[black2.i][black2.j] == 0) {
blackblocks.push_back(black1);
blackblocks.push_back(black2);
}
}
if (block == 4) {
Pos black1{ pos1.i, pos1.j - 1 }; Pos black2{ pos1.i + 1, pos1.j - 1 };
if (Board[black1.i][black1.j] == 0 && Board[black2.i][black2.j] == 0) {
blackblocks.push_back(black1);
blackblocks.push_back(black2);
}
}
if (block == 6) {
Pos black1{ pos1.i, pos1.j + 1 }; Pos black2{ pos1.i + 1, pos1.j + 1 };
if (Board[black1.i][black1.j] == 0 && Board[black2.i][black2.j] == 0) {
blackblocks.push_back(black1);
blackblocks.push_back(black2);
}
}
if (block == 7) {
Pos black1{ pos1.i, pos1.j - 2 }; Pos black2{ pos1.i, pos1.j - 1 };
if (Board[black1.i][black1.j] == 0 && Board[black2.i][black2.j] == 0) {
blackblocks.push_back(black1);
blackblocks.push_back(black2);
}
}
if (block == 9) {
Pos black1{ pos1.i, pos1.j - 1 }; Pos black2{ pos1.i, pos1.j + 1 };
if (Board[black1.i][black1.j] == 0 && Board[black2.i][black2.j] == 0) {
blackblocks.push_back(black1);
blackblocks.push_back(black2);
}
}
return blackblocks;
}
// 블록 지우기 (하나의 블록을 이루는 4 개의 1x1 블록 지우기)
void EraseBlock(Block block) {
Board[block.pos1.i][block.pos1.j] = 0;
Board[block.pos2.i][block.pos2.j] = 0;
Board[block.pos3.i][block.pos3.j] = 0;
Board[block.pos4.i][block.pos4.j] = 0;
}
int solution(vector<vector<int>> board) {
int answer = 0;
Board = board;
N = board.size();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (Board[i][j] == 0) continue; // 빈 공간이면 넘어감
if (Checked[Board[i][j]]) continue; // 이미 제거했거나 제거 불가능한 종류의 블록으로 판명난 블록이면 넘어감
Pos startPos;
// 처음으로 만난 value 값일 때 이곳에 걸릴 것이고 Start 에 블록 시작 위치(pos1 1x1)를 저장한다.
if (Start.find(Board[i][j]) == Start.end()) {
startPos.i = i; startPos.j = j;
Start[Board[i][j]] = startPos;
}
// 이곳에 걸리는 블록은 제거 가능한 블록인데 지난번에 제거되지 못한 블록일 것이다. 장애물들이 제거된 상태에서 다시 찾아왔따면 이번엔 제거될 수도 있으니 한번 더 시도해보자!
// 블록은 pos1 기준으로 판별하도록 함수를 짜놨기 때문에 해당 value 값을 통하여 저장해두었던 시작 위치를 startPos 에 불러 옴
else startPos = Start[Board[i][j]];
int blockNum = BlockName(startPos, Board[i][j]); // 블록 종류
// 제거 가능한 블록이라면 (3,4,6,7,9)
if (IsErasableBlock(blockNum)) {
// blockNum 종류 블록의 검은 블록이 놓일 수 있는 두 위치가 담긴 벡터
vector<Pos> blackblocks = BlackBlock(startPos, blockNum);
if (blackblocks.empty()) continue; // 비어 있다면 현재 board 상태로는 두 검은 블록이 놓일 수 없으므로 (두 자리에 장애물이 있는 상태) 넘어감
bool obstacle = false;
// 두 검은 블록 가능 위치의 위에 장애물(board값이 0이 아닌) 블록이 있는지 쭉 검사. 하나라도 있으면 안됨.
for (int i = blackblocks[0].i; i >= 0; --i) {
if (Board[i][blackblocks[0].j] != 0) {
obstacle = true;
break;
}
}
if (obstacle) continue;
for (int i = blackblocks[1].i; i >= 0; --i) {
if (Board[i][blackblocks[1].j] != 0) {
obstacle = true;
break;
}
}
if (obstacle) continue;
// 여기까지 도착했다면 제거 가능한 블록이니 제거하자!
Block block = BlockPos(startPos, blockNum);
EraseBlock(block);
Checked[Board[i][j]] = true; // 제거 완료 하였으니 다음엔 이 value 값의 블록은 검사 안하고 넘어가도록
answer++; // 카운팅 -*
}
// 제거 가능한 블록이 아니라면
else
Checked[Board[i][j]] = true; // 다음엔 이 value 값의 블록은 검사 안하고 넘어가도록
}
}
return answer;
}
🚀 다른 풀이
뭔가 같은 카카오 공채 문제인 자물쇠와 열쇠 문제와 풀이 방법이 비슷하다고 느꼈다. 이 문제에선 제거되는 직사각형은 늘 2 x 3 크기이기 때문에 범위를 가로가 긴 2 x 3 직사각형 범위로 놓고 제거될 수 있는 블록을 찾고, 세로로 긴 3 x 2 직사각형 범위로 놓고 또 제거 될 수 있는 블록을 찾으며 순회를 한다. 이 직사각형 범위 안에 제거될 수 있는 블록은 1 x 1 단위로 4 개 되야 하며(다 같은 값으로만 이루어져야 함) 블랙 블록이 놓일 수 있는 곳은 2 개가 되야한다. (마찬가지로 위의 행에 다 0 이어야 함)
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기