문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 1) 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 2) 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, 3) |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 4) 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다.5) 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 6) 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 7) 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 8) 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
- 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
- 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
- 격자에 중력이 작용한다.
- 격자가 90도 반시계 방향으로 회전한다.
- 다시 격자에 중력이 작용한다.
9) 격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
다음은 N = 5, M = 3인 경우의 예시이다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
블록 그룹이 제거되면 다음과 같이 변하고, 점수 82점을 획득한다.
| 2 | 2 | -1 | 3 | 1 |
| 2 | 0 | -1 | ||
| 1 | 2 | |||
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 1 |
중력이 작용하면 다음과 같이 변한다.
| -1 | 3 | 1 | ||
| 0 | -1 | |||
| 2 | 2 | 1 | 2 | |
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 2 | 1 |
90도 반시계방향으로 회전한 결과는 다음과 같다.
| 1 | -1 | 2 | 2 | 1 |
| 3 | 0 | 1 | 3 | 2 |
| -1 | 2 | 1 | 2 | |
| 2 | ||||
| 2 | -1 |
다시 여기서 중력이 작용하면 다음과 같이 변한다.
| 1 | -1 | |||
| 3 | 2 | 2 | 1 | |
| -1 | 1 | 3 | 2 | |
| 2 | 1 | 2 | ||
| 0 | 2 | -1 | 2 |
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.
입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
제한
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 5
구현해야할 조건
블록이 세가지가 있습니다. 블랙, 레인보우, 노멀 이중 노멀은 1~M가지의 색깔로 이루어져 있다.
조건을 보면 그룹에는 일반 블록이 적어도 하나 있어야한다. 이말인 즉 일반 블록으로 그룹을 시작해야한다. rainbow는 기준이 될수 없다 라는 점. 일반 블록의 색은 모두 같아야 한다. 무지개 블록은 어디든 포함될 수 있다!
그룹에 속한 블록의 개수는 2보다 크거나 같아야한다. 2이상이 되어야 하고, 인접한 칸으로 이동이 가능해야 한다. 이 말인 즉 BFS를 통해서 찾아내라는 의미이다. 기준블록을 결정을 하는데 기준블록은 무지개 블록이 아니여야 한다는 점에서 그룹 시작점으로 사용이 될 수 있다. 하지만 여러가지 방면으로 봤을때 vector에 전부 집어넣어서 sort과정을 해야 된다고 생각했다. 이 부분이 함정이 가장 많은 부분이라고 생각 된다.
오토 플레이는 간단하게 구현을 해주면 된다.
code
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX 21
using namespace std;
typedef struct{
int y;
int x; // 기준 블록
int cnt; // group cnt
int rainbow;
}Block;
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0}; // down, up, right, left
int n,m;
int res = 0;
int board[MAX][MAX];
bool visited[MAX][MAX];
vector<Block> blocks;
bool comp(pair<int,int> &a, pair<int,int> &b)
{
if(a.first == b.first)
return a.second < b.second;
return a.first < b.first; // 기준 블록 정해주는 것
}
bool block_comp(Block &a, Block &b) // 정렬조건을 정확히 읽자 제발!!
{
if(a.cnt == b.cnt)
{
if(a.rainbow == b.rainbow)
{
if(a.y == b.y)
{
return a.x > b.x;
}
return a.y > b.y;
}
return a.rainbow > b.rainbow;
}
return a.cnt > b.cnt;
}
void print()
{
cout << "\n";
cout << "\n";
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cout << board[i][j] << " ";
}
cout << endl;
}
}
void BFS(int y, int x, int color)
{
memset(visited,false,sizeof(visited));
int cnt = 1; // color & rainbow count
int rainbow = 0;
vector<pair<int,int> > v;
queue<pair<int,int> > q;
v.clear();
q.push({y,x}); // first : y, second : x;
visited[y][x] = true; // visit grid
v.push_back({y,x}); // main y,x
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(0 <= nx && nx < n && 0 <= ny && ny < n && !visited[ny][nx]) // range
{ //range, visited
if(board[ny][nx] == 0)
{
visited[ny][nx] = true;
q.push({ny,nx});
cnt++; // count chk
rainbow++;
}
else if(board[ny][nx] == color)
{
visited[ny][nx] = true;
q.push({ny,nx});
cnt++;
v.push_back({ny,nx}); // main block chk
}
}
}
}
sort(v.begin(), v.end(), comp); // main block sorting
if(cnt >= 2) // 크기가 2 이상
blocks.push_back({v[0].first,v[0].second,cnt,rainbow});
return;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> board[i][j];
}
}
while(1)
{
blocks.clear();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(board[i][j] >= 1 && board[i][j] <= m)
BFS(i,j,board[i][j]); // y,x, block_color;
}
}
if(blocks.size() == 0)
break;
sort(blocks.begin(), blocks.end(), block_comp);
//delete
memset(visited,0,sizeof(visited));
queue<pair<int,int> > q;
q.push({blocks[0].y, blocks[0].x});
int score = 1; // 처음 값 넣어주는거 잊지마.
int color = board[blocks[0].y][blocks[0].x]; // color 구했고
board[blocks[0].y][blocks[0].x] = -2; // -2로 삭제
visited[blocks[0].y][blocks[0].x] = true; // 방문까지
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(0 <= nx && nx < n && 0 <= ny && ny < n && !visited[ny][nx])
{
if(board[ny][nx] == 0 || board[ny][nx] == color)
{
score++;
board[ny][nx] = -2;
visited[ny][nx] = true;
q.push({ny,nx});
}
}
}
}
// cout << endl;
// cout << "Delete status" << endl;
// print();
//
// cout << "Score : " << score << endl;
res += score*score;
for(int i = 0; i < n; i++)
{
int index = n-1;
queue<int> q;
for(int j = n - 1; j >= 0; j--)
{
if(board[j][i] == -1)
{
while(!q.empty())
{
board[index][i] = q.front();
q.pop();
index--;
}
index = j-1;
}
else if(board[j][i] >= 1 && board[j][i] <= m || board[j][i] == 0)
{
q.push(board[j][i]);
board[j][i] = -2;
}
}
while(!q.empty())
{
board[index][i] = q.front();
q.pop();
index--;
}
}
// cout << endl;
// cout <<"G status" << endl;
//
// print();
//반시계 방향
int tempBoard[MAX][MAX];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
tempBoard[n-1-j][i] = board[i][j];
}
}
//중력
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
board[i][j] = tempBoard[i][j];
}
}
// cout << endl;
// cout << "Counter clock status" << endl;
// print();
//
for(int i = 0; i < n; i++)
{
int index = n-1;
queue<int> q;
for(int j = n - 1; j >= 0; j--)
{
if(board[j][i] == -1)
{
while(!q.empty())
{
board[index][i] = q.front();
q.pop();
index--;
}
index = j-1;
}
else if(board[j][i] >= 1 && board[j][i] <= m || board[j][i] == 0)
{
q.push(board[j][i]);
board[j][i] = -2;
}
}
while(!q.empty())
{
board[index][i] = q.front();
q.pop();
index--;
}
}
// cout << endl;
// cout << "2nd G status" << endl;
// cout << endl;
// print();
}
cout << res;
return 0;
}
code [함수를 나눠서 문제를 다시 풀어봤습니다!]
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAX 21
using namespace std;
typedef struct{
int y;
int x; // main block location
int cnt; // group block cnt
int rainbow; // rainbow cnt
}Group;
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
int n,m;
int board[MAX][MAX];
bool visited[MAX][MAX];
vector<Group> groups;
bool comp(pair<int,int> &a, pair<int,int> &b){
if(a.first == b.first){
return a.second < b.second;
}
return a.first < b.first;
} // 조건을 꼼꼼히 읽읍십다!
bool group_comp(Group &a, Group &b){
if(a.cnt == b.cnt){
if(a.rainbow == b.rainbow){
if(a.y == b.y){
return a.x > b.x;
}
return a.y > b.y;
}
return a.rainbow > b.rainbow;
}
return a.cnt > b.cnt;
} // 조건을 꼼꼼히 읽읍십다!!
void BFS(int y, int x, int color){
memset(visited,false,sizeof(visited)); // 방문을 하려면 visited를 초기화
int cnt = 1;
int rainbow = 0;
visited[y][x] = true;
vector<pair<int,int> > v;
queue<pair<int,int> > q;
v.push_back({y,x}); // 블록이 들어갑니다.
q.push({y,x}); // 블록이 전체 몇개? 레인보우 몇개 탐색!
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(0 <= nx && nx < n && 0 <= ny && ny < n){
if(!visited[ny][nx] && board[ny][nx] != -1) // 방문하지 않았고, -1이 아니라면
{
if(board[ny][nx] == color){ // normal block
cnt++;
visited[ny][nx] = true;
v.push_back({ny,nx}); // 기준 블록을 정해야하기 때문에 vector에 넣어주기
q.push({ny,nx});
}
else if(board[ny][nx] == 0){ // rainbow block
rainbow++;
cnt++;
visited[ny][nx] = true;
q.push({ny,nx});
}
}
}
}
}
sort(v.begin(),v.end(),comp); // vector에서 기준 블록을 찾아줍니다.
if(cnt >= 2){ // 2개 이상만 블록 그룹으로 들어갈 수 있습니다.
groups.push_back({v[0].first, v[0].second, cnt, rainbow});
}
}
int DeleteBFS(int y, int x)
{
memset(visited,false,sizeof(visited));
queue<pair<int,int> >q;
q.push({y,x});
int cnt = 0;
int color = board[y][x];
visited[y][x] = true;
board[y][x] = -2; // 바꿔주기
while(!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(0 <= nx && nx < n && 0 <= ny && ny < n){
if(!visited[ny][nx] && board[ny][nx] != -1){
if(board[ny][nx] == color){
visited[ny][nx] = true;
q.push({ny,nx});
}
else if(board[ny][nx] == 0){
visited[ny][nx] = true;
q.push({ny,nx});
}
}
}
}
}
// 우선으로 지워주기 시작하면 문제가 발생하니까 한번에 지워줍시다.
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(visited[i][j]){
cnt++;
board[i][j] = -2;
}
}
}
return cnt * cnt;
}
void gravity()
{
for(int i = 0; i < n; i++){
int idx = n - 1; // 마지막 부터
queue<int> q;
for(int j = n - 1; j >= 0; j--){
if(board[j][i] == -2)
continue;
else if(board[j][i] == -1){
//-1은 즉 새로운 벽이라고 생각하지
while(!q.empty())
{
int data = q.front();
q.pop();
board[idx][i] = data;
idx--;
}
idx = j - 1; // 한칸 위에서 부터 시작을 해야함
}
else{
q.push(board[j][i]);
board[j][i] = -2;
}
}
//남은 큐들 넣어주기
while(!q.empty()){
int data = q.front();
q.pop();
board[idx][i] = data;
idx--;
}
}
}
void counter_clock()
{
int temp[MAX][MAX];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
temp[i][j] = board[j][n - i - 1];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
board[i][j] = temp[i][j];
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> board[i][j];
}
} //input board, 블럭들을 다 담는 배열입니다.
int sum = 0; // 전체 합을 구해주고
while(1)
{
groups.clear();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(1 <= board[i][j] && board[i][j] <= m){
BFS(i,j,board[i][j]); // 기준블록은 언제나 숫자만 허용되기때문에!
}
}
}
if(groups.size() == 0)
break; // 시뮬레이션 종료 조건!
sort(groups.begin(), groups.end(), group_comp);
sum += DeleteBFS(groups[0].y, groups[0].x);
gravity(); // 시계 반대방향으로 이동, 이건 그냥 장난치는 것 같다.
counter_clock();
gravity(); // 마지막 돌려주
}
cout << sum;
return 0;
}'PS > Samsung' 카테고리의 다른 글
| [백준/c++] 23290 마법사 상어와 복제 (0) | 2022.04.12 |
|---|---|
| [백준/c++] 21608 상어 초등학교 (0) | 2022.04.07 |
| [백준/c++] 20058 마법사 상어와 파이어스톰 (0) | 2022.04.06 |
| [백준/c++] 20057 마법사 상어와 토네이도 (0) | 2022.04.06 |
| [백준/c++] 23288 주사위 굴리기2 (0) | 2022.02.24 |
