프로그래머스
[프로그래머스/Level 3/C++] 퍼즐 조각 채우기
Vfly
2023. 1. 10. 23:17
https://school.programmers.co.kr/learn/courses/30/lessons/84021
- 출처 : 프로그래머스 코딩 테스트 연습
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 요약]
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
- 위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다.
- 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다.
- 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
[문제 조건]
- 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
[문제 풀이]
대단한 알고리즘은 없지만 구현하는데 그냥 힘든 문제였다.
문제에서 원하는건 table에서 조각을 찾아 game_board에 정확하게 빈 곳 없이 딱 맞게 들어가는 조각들의 1x1 정사각형의 갯수를 구하면 된다.
필자는 table배열과 game_board배열에서 각각 BFS를 이용하여 조각과 빈 공간에 대한 정보를 table_blocks와 board_blocks에 좌표 형태( pair<int,int> ) 형태로 저장했다.
주어지는 배열에서 조각과 빈 공간 찾기
vector<vector<pii>> make_blocks(int n, int m, int target, vector<vector<int>> &table, vector<vector<bool>> &ck)
{
vector<vector<pii>> blocks;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(table[i][j] != target || ck[i][j]) continue;
queue<pii> q;
vector<pii> block;
block.push_back({i,j});
q.push({i,j}); ck[i][j] = true;
while(!q.empty())
{
pii tmp = q.front(); q.pop();
for(int k=0; k<4; k++)
{
int nx = tmp.second + dx[k];
int ny = tmp.first + dy[k];
if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if(ck[ny][nx]) continue;
if(table[ny][nx] != target) continue;
ck[ny][nx] = true;
q.push({ny,nx});
block.push_back({ny,nx});
}
}
blocks.push_back(block);
}
}
return blocks;
}
///////////////////////////////////
...................................
///////////////////////////////////
table_blocks = make_blocks(n, m, 1, table, ck);
for(int i=0; i<n; i++) for(int j=0; j<m; j++) ck[i][j] = false;
board_blocks = make_blocks(n, m, 0, game_board, ck);
이 좌표형태로 되어 있는 배열을 다시 가공하여 2차원 배열에 알맞게 가공하였다.
좌표형태로 된 조각들 2차원 배열 형태의 사각형으로 가공하는 코드
vector<vector<int>> make_square(vector<pii> input)
{
vector<vector<int>> square;
int max_y = 0; int min_y = 99;
int max_x = 0; int min_x = 99;
for(int i=0; i<input.size(); i++)
{
max_y = max(max_y, input[i].first);
min_y = min(min_y, input[i].first);
max_x = max(max_x, input[i].second);
min_x = min(min_x, input[i].second);
}
int n = max_y - min_y + 1;
int m = max_x - min_x + 1;
square.resize(n);
for(int i=0; i<n; i++) square[i].resize(m);
for(int i=0; i<input.size(); i++)
{
square[input[i].first-min_y][input[i].second-min_x] = 1;
}
return square;
}이렇게 가공한 2차원 배열들은 table의 조각들은 table_block_square 배열에다가, game_board의 조각들은 board_block_square에 저장했다.
그리고 이 조각들을 하나씩 비교하면서 들어갈 수 있는지 없는지 판별하여 들어 갈 수 있다면 조각에서의 1x1정사각형의 개수를 세어서 answer에 추가하는 방식이다.
그리고 조각들끼리 비교할때 각 조각들은 회전시킬 수 있다고 했으므로 각 조각끼리 비교할때 행과 열의 길이가 같을 때는 조각이 같은지 판별하고 행과 열의 길이가 같지 않거나 서로 다르면 회전시켜서 다시 비교하는 방식으로 코드를 작성했다.
조각 회전 코드
pii ck_same_square(vector<vector<int>> &a, vector<vector<int>> &b)
{
int cnt =0;
for(int i=0; i<a.size(); i++)
{
for(int j=0; j<a[i].size(); j++)
{
if(a[i][j] != b[i][j])
{
return {0,0};
}
else
{
if(a[i][j] == 1) cnt++;
}
}
}
return {1,cnt};
}- 위 코드에서 리턴 값의 첫번째는 서로 같을 경우는 1, 다르면 0을 가진다. 두번째 값은 같았을 경우를 대비한 1x1정사각형의 개수를 의미한다.
조각들을 비교하여 정답을 구하는 코드
vector<bool> ck_block_use_table; ck_block_use_table.resize(table_block_square.size());
for(int i=0; i<board_block_square.size(); i++)
{
for(int j=0; j<table_block_square.size(); j++)
{
if(ck_block_use_table[j]) continue;
bool fin = false;
for(int k=0; k<4; k++)
{
int row = table_block_square[j].size();
int col = table_block_square[j][0].size();
if(row==board_block_square[i].size() && col==board_block_square[i][0].size())
{
pii tmp = ck_same_square(board_block_square[i], table_block_square[j]);
if(tmp.first == 1)
{
answer += tmp.second; ck_block_use_table[j] = true;
fin = true;
break;
}
else
{
table_block_square[j] = spin_square(table_block_square[j]);
}
}
else table_block_square[j] = spin_square(table_block_square[j]);
}
if(fin) break;
}
}- table의 조각을 두번 이상 board에 넣는 오류를 방지하기 위해 조각 사용 여부 배열을 하나두어 비교하였다.
[전체 소스 코드]
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#define pii pair<int,int>
using namespace std;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<vector<int>> make_square(vector<pii> input)
{
vector<vector<int>> square;
int max_y = 0; int min_y = 99;
int max_x = 0; int min_x = 99;
for(int i=0; i<input.size(); i++)
{
max_y = max(max_y, input[i].first);
min_y = min(min_y, input[i].first);
max_x = max(max_x, input[i].second);
min_x = min(min_x, input[i].second);
}
int n = max_y - min_y + 1;
int m = max_x - min_x + 1;
square.resize(n);
for(int i=0; i<n; i++) square[i].resize(m);
for(int i=0; i<input.size(); i++)
{
square[input[i].first-min_y][input[i].second-min_x] = 1;
}
return square;
}
vector<vector<pii>> make_blocks(int n, int m, int target, vector<vector<int>> &table, vector<vector<bool>> &ck)
{
vector<vector<pii>> blocks;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(table[i][j] != target || ck[i][j]) continue;
queue<pii> q;
vector<pii> block;
block.push_back({i,j});
q.push({i,j}); ck[i][j] = true;
while(!q.empty())
{
pii tmp = q.front(); q.pop();
for(int k=0; k<4; k++)
{
int nx = tmp.second + dx[k];
int ny = tmp.first + dy[k];
if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if(ck[ny][nx]) continue;
if(table[ny][nx] != target) continue;
ck[ny][nx] = true;
q.push({ny,nx});
block.push_back({ny,nx});
}
}
blocks.push_back(block);
}
}
return blocks;
}
vector<vector<int>> spin_square(vector<vector<int>> &input)
{
int n = input.size();
int m = input[0].size();
vector<vector<int>> new_square;
new_square.resize(m);
for(int i=0; i<m; i++) new_square[i].resize(n);
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
new_square[i][j] = input[n-1-j][i];
}
}
return new_square;
}
pii ck_same_square(vector<vector<int>> &a, vector<vector<int>> &b)
{
int cnt =0;
for(int i=0; i<a.size(); i++)
{
for(int j=0; j<a[i].size(); j++)
{
if(a[i][j] != b[i][j])
{
return {0,0};
}
else
{
if(a[i][j] == 1) cnt++;
}
}
}
return {1,cnt};
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
int answer = 0;
int n = table.size();
int m = table[0].size();
vector<vector<pii>> table_blocks;
vector<vector<pii>> board_blocks;
vector<vector<bool>> ck; ck.resize(n);
for(int k=0; k<n; k++) ck[k].resize(m);
table_blocks = make_blocks(n, m, 1, table, ck);
for(int i=0; i<n; i++) for(int j=0; j<m; j++) ck[i][j] = false;
board_blocks = make_blocks(n, m, 0, game_board, ck);
vector<vector<vector<int>>> table_block_square;
vector<vector<vector<int>>> board_block_square;
for(int i=0; i<table_blocks.size(); i++)
table_block_square.push_back(make_square(table_blocks[i]));
for(int i=0; i<board_blocks.size(); i++)
board_block_square.push_back(make_square(board_blocks[i]));
vector<bool> ck_block_use_table; ck_block_use_table.resize(table_block_square.size());
for(int i=0; i<board_block_square.size(); i++)
{
for(int j=0; j<table_block_square.size(); j++)
{
if(ck_block_use_table[j]) continue;
bool fin = false;
for(int k=0; k<4; k++)
{
int row = table_block_square[j].size();
int col = table_block_square[j][0].size();
if(row==board_block_square[i].size() && col==board_block_square[i][0].size())
{
pii tmp = ck_same_square(board_block_square[i], table_block_square[j]);
if(tmp.first == 1)
{
answer += tmp.second; ck_block_use_table[j] = true;
fin = true;
break;
}
else
{
table_block_square[j] = spin_square(table_block_square[j]);
}
}
else table_block_square[j] = spin_square(table_block_square[j]);
}
if(fin) break;
}
}
return answer;
}막 엄청난 알고리즘이 들어간건 아니였지만 구현하는데 시간이 오래 걸렸던 문제였다.
굳