문제
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
풀이
#include <string>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
struct Point {
int x, y;
Point(int x, int y): x(x), y(y) {}
};
void normalizePoints(vector<Point> &v) {
int min_x = INT_MAX;
int min_y = INT_MAX;
for (auto p:v) {
min_x = (min_x < p.x)? min_x : p.x;
min_y = (min_y < p.y)? min_y : p.y;
}
for (auto &p:v) {
p.x -= min_x;
p.y -= min_y;
}
sort(v.begin(), v.end(), [](Point a, Point b) {
if (a.x==b.x) return a.y < b.y;
return a.x < b.x;
});
}
void rotatePuzzle(vector<Point> &v) {
int max_x = 0;
int max_y = 0;
for (auto &p:v) {
max_x = (max_x > p.x)? max_x : p.x;
max_y = (max_y > p.y)? max_y : p.y;
}
int max_n = (max_x > max_y)? max_x : max_y;
for (auto &p : v) {
int old_x = p.x;
int old_y = p.y;
p.x = max_n - old_y;
p.y = old_x;
}
normalizePoints(v);
}
bool checkMatch(vector<Point> s, vector<Point> p) {
if (s.size()!=p.size()) return false;
for (int i=0; i<s.size(); i++) {
if (s[i].x!=p[i].x || s[i].y!=p[i].y) return false;
}
return true;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
int answer = 0;
vector<vector<Point>> space;
vector<vector<Point>> puzzles;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 보드 빈 공간 뽑기 bfs
vector<vector<int>> visit(game_board.size(), vector<int> (game_board.size()));
queue<Point> q;
for (int i=0; i<game_board.size(); i++){
for (int j=0; j<game_board.size(); j++) {
if (game_board[i][j]==0 && visit[i][j]==0) {
q.push(Point(j, i));
visit[i][j]=1;
vector<Point> area;
while (!q.empty()) {
Point cur = q.front();
q.pop();
area.push_back(cur);
for (int k=0; k<4; k++) {
int new_x = cur.x + dx[k];
int new_y = cur.y + dy[k];
if (new_x < 0 || new_y < 0 || new_x >= game_board.size() || new_y >= game_board.size()) continue;
if (visit[new_y][new_x]!=0 || game_board[new_y][new_x]!=0) continue;
q.push(Point(new_x, new_y));
visit[new_y][new_x]=1;
}
}
normalizePoints(area);
space.push_back(area);
}
}
}
// 퍼즐 조각 뽑기 bfs
vector<vector<int>> visit_puzzle(game_board.size(), vector<int> (game_board.size()));
queue<Point> q_puzzle;
for (int i=0; i<table.size(); i++){
for (int j=0; j<table.size(); j++) {
if (table[i][j]==1 && visit_puzzle[i][j]==0) {
q_puzzle.push(Point(j, i));
visit_puzzle[i][j]=1;
vector<Point> puzzle;
while (!q_puzzle.empty()) {
Point cur = q_puzzle.front();
q_puzzle.pop();
puzzle.push_back(cur);
for (int k=0; k<4; k++) {
int new_x = cur.x + dx[k];
int new_y = cur.y + dy[k];
if (new_x < 0 || new_y < 0 || new_x >= table.size() || new_y >= table.size()) continue;
if (visit_puzzle[new_y][new_x]!=0 || table[new_y][new_x]!=1) continue;
q_puzzle.push(Point(new_x, new_y));
visit_puzzle[new_y][new_x]=1;
}
}
normalizePoints(puzzle);
puzzles.push_back(puzzle);
}
}
}
// 매칭되는지 확인 삼중 for 문
// 1. 빈공간 2. 퍼즐 3. 회전
vector<int> space_check(space.size());
vector<int> puzzle_check(puzzles.size());
for (int s=0; s<space.size(); s++) {
for (int p=0; p<puzzles.size(); p++) {
auto sp = space[s];
auto pu = puzzles[p];
if (space_check[s]) continue;
if (puzzle_check[p]) continue;
for (int i=0; i<4; i++) {
// 매칭 확인
bool match = checkMatch(sp, pu);
if (match) {
answer+= sp.size();
space_check[s] = 1;
puzzle_check[p] = 1;
break;
}
else rotatePuzzle(pu);
}
}
}
return answer;
}