Problem Solving/BOJ(백준)
[BOJ]백준 21609번: 상어 중학교(C++)/Simulation
이진2
2021. 6. 14. 03:11
https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
내가 삼성 코테에서 접한 삼성 유형의 정수라고 할 수 있는 문제
시뮬레이션+DFS+중력+배열회전이 전부 합쳐져서 처음 문제를 봤을 때 그냥 웃겼다
요즘 삼성 유형은 주사위 윷놀이같은 끔찍한 문제가 더 안 나오는 걸 보니 이전보다 난이도를 낮추고 구현 능력에 포커스를 맞춘 것 같아 보인다
상어 초등학교는 너무 쉬워서 당황했지만 상어 중학교는 요구사항이 엄청엄청엄청 많기 때문에 잘 정리하고 설계해야 한다
나도 아래처럼 설계했음에도 그룹의 행열 우선순위와 기준블록의 행열 우선순위가 다른 것이 헷갈려서 잘못 구현했다
보통 이런식으로 설계한 뒤 input 케이스들을 확인해보고, 틀렸다면 1️⃣함수 수도코드가 정확한지 2️⃣요구사항 정리->함수 설계로 갈 때 빼먹은 조건이 있는지 3️⃣문제의 조건들이 빠짐없이 정리 되었는지 등을 검사한다
보통 123번 안에 실수한 것이 있다
현재는 삼성 유형은 큰 어려움 없이 요구사항 정리 -> 설계 -> 구현 순으로 짤 수 있지만 아직 Not 삼성 유형은 그렇게까진 못하겠다
방학 때 문제 많이많이 풀어야지
#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>
#define pii pair<int,int>
#define BLACK -1
#define RAINBOW 0
#define AIR -2
using namespace std;
typedef struct { int x, y; }point;
int n, m, board[21][21],ans;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
bool visit[21][21];
bool safe(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
pii dfs(point cur,int color) {
visit[cur.y][cur.x] = 1;
pii score = make_pair(0, 0);
if (board[cur.y][cur.x] == RAINBOW)score.second++;
else if (board[cur.y][cur.x] == color)score.first++;
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (safe(nx,ny)&&!visit[ny][nx] && (board[ny][nx] == color || board[ny][nx] == RAINBOW)) {
auto ret = dfs({ nx,ny }, color);
score.first += ret.first;
score.second += ret.second;
}
}
return score;
}
void popBlock(point cur, int color) {
board[cur.y][cur.x] = AIR;
visit[cur.y][cur.x] = 1;
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (safe(nx, ny) && !visit[ny][nx] && (board[ny][nx] == color || board[ny][nx] == RAINBOW)) {
popBlock({ nx,ny }, color);
}
}
}
void gravity() {
for(int j=0;j<n;j++)
for (int i = n - 1; i >= 0; i--) {
if (board[i][j] < 0)continue;
int cur=i,next=i+1;
while (safe(j, next)&&board[next][j]==AIR) {
board[next][j] = board[cur][j];
board[cur][j] = AIR;
cur++;
next++;
}
}
}
void rotate() {
int temp[21][21];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp[i][j] = board[j][n - 1 - i];
memcpy(board, temp, sizeof(temp));
}
bool game() {
pii score=make_pair(0,0);
point block = { -1,-1 };
memset(visit, false, sizeof(visit));
for(int i=0;i<n;i++)
for (int j = 0; j < n; j++) {
if (board[i][j] <= 0)continue;
point cur = { j,i };
auto x = dfs(cur, board[i][j]);
for (int a = 0; a < n; a++)for (int b = 0; b < n; b++)if (board[a][b] == RAINBOW)visit[a][b] = false;
if (x.first + x.second < 2)continue;
if ((x.first + x.second > score.first + score.second)
||((x.first+x.second==score.first+score.second)&&(x.second>score.second))
|| ((x.first + x.second == score.first + score.second) && (x.second == score.second)&&(i>block.y))
|| ((x.first + x.second == score.first + score.second) && (x.second == score.second) && (i == block.y&&j>block.x))) {
score = x;
block = { j,i };
}
}
memset(visit, false, sizeof(visit));
if (block.x != -1) {
ans += pow(score.first + score.second, 2);
popBlock(block, board[block.y][block.x]);
gravity();
rotate();
gravity();
return true;
}
else return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &board[i][j]);
while (game());
printf("%d", ans);
return 0;
}
그리고 테스트케이스 예제 2번이 이해가 안 가서 디버깅할 때 힘들었는데 내가 구현한 동작과정 또한 첨부한당 ~_~
더보기
current score: 0
------------
2 3 1 R B 2
2 B 4 1 3 3
3 R 4 2 2 1
B 4 B 2 3 4
3 B 4 2 R 3
1 2 2 2 2 1
------------
------------
2 3 1 R B 2
2 B 4 1 3 3
3 R 4 1
B 4 B 3 4
3 B 4 3
1 1
------------
------------
2
B 3 1
3 1 4 3 3
1 4 4 B R 1
3 B R 4 B 4
2 2 3 B 3 1
------------
current score: 81
------------
2
B 3 1
3 1 4 3 3
1 4 4 B R 1
3 B R 4 B 4
2 2 3 B 3 1
------------
------------
2
B 3 1
3 1 4 3 3
1 B R 1
3 B B 4
2 2 3 B 3 1
------------
------------
1 4 1
R B 3
B B
1 3 1 3
3 3 3 B 2
2 B 4 1 3 2
------------
current score: 97
------------
1 4 1
R B 3
B B
1 3 1 3
3 3 3 B 2
2 B 4 1 3 2
------------
------------
1 4 1
R B 3
B B
1 1 3
B 2
2 B 4 1 3 2
------------
------------
3 B 2 2
B B 3
B 1
1 4
4 3 B
1 R 1 1 2
------------
current score: 113
------------
3 B 2 2
B B 3
B 1
1 4
4 3 B
1 R 1 1 2
------------
------------
3 B 2 2
B B 3
B 1
1 4
4 3 B
1 1 2
------------
------------
3 B
2 B
2 1 2
B B 1
B 3 1
3 4 1 4
------------
current score: 117
------------
3 B
2 B
2 1 2
B B 1
B 3 1
3 4 1 4
------------
------------
3 B
2 B
2 1 2
B B
B 3
3 4 1 4
------------
------------
B
2 4
B 3 1
B 1 B 4
3 2 2 B 3
------------
current score: 121
------------
B
2 4
B 3 1
B 1 B 4
3 2 2 B 3
------------
------------
B
2 4
B 3 1
B 1 B 4
3 B 3
------------
------------
1 4
3 B 3
B B
4 B 1
B 2 3
------------
current score: 125
------------
1 4
3 B 3
B B
4 B 1
B 2 3
------------