[BOJ]백준 21609번: 상어 중학교(C++)/Simulation

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

내가 삼성 코테에서 접한 삼성 유형의 정수라고 할 수 있는 문제

시뮬레이션+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
------------