백준 - 상어 중학교 (21609)

1. 문제 링크

문제 링크

2. 풀이

1. 삭제할 블록 그룹이 있을 때까지 삭제하기

bool addScoreAndRemoveBlockIfFind() {
	int maxBlockSize = 1, maxRainBowCnt = 0, maxY = -1, maxX = -1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] <= 0 || visited[i][j] == 1) continue;

			int rainBowCnt = 0;
			int blockColor = board[i][j];

			q.push({ i, j });
			tq.push({ i, j });
			visited[i][j] = 1;

			while (!q.empty()) {
				int y = q.front().first;
				int x = q.front().second;

				q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

					if (board[ny][nx] != RAINBOW && board[ny][nx] != blockColor) continue;

					if (visited[ny][nx] == 1) continue;

					// 무지개일 때 
					if (board[ny][nx] == RAINBOW) {
						// 무지개 카운트 증가
						rainBowCnt++;
						// 무지개 큐에 푸시
						rq.push({ ny, nx });
					}

					q.push({ ny, nx });
					tq.push({ ny, nx });
					visited[ny][nx] = 1;
				}
			}

			int blockSize = tq.size();

			// 블록 크기가 이전 블록보다 클 때
			if (blockSize > maxBlockSize) {
				maxBlockSize = blockSize;
				maxRainBowCnt = rainBowCnt;
				maxY = i;
				maxX = j;
				dq = tq;
			}
			// 블록 크기가 같고 무지개 수가 많을 때
			else if (blockSize == maxBlockSize && rainBowCnt > maxRainBowCnt) {
				maxRainBowCnt = rainBowCnt;
				maxY = i;
				maxX = j;
				dq = tq;
			}
			// 블록 크기가 같고 무지개 수도 같고
			else if (blockSize == maxBlockSize && rainBowCnt == maxRainBowCnt) {
				// 행이 작거나, 행이 같고 열이 작을 때
				if (i > maxY || (i == maxY && j > maxX)) {
					maxY = i;
					maxX = j;
					dq = tq;
				}
			}

			// 무지개 블록은 visited 초기화
			while (!rq.empty()) {
				visited[rq.front().first][rq.front().second] = 0;
				rq.pop();
			}

			while (!tq.empty()) tq.pop();
		}
	}

	// 삭제할 블록이 없을 때
	if (maxBlockSize == 1) return false;

	// 블록 삭제
	while (!dq.empty()) {
		int y = dq.front().first;
		int x = dq.front().second;

		dq.pop();
		board[y][x] = EMPTY;
	}

	// visited 초기화
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visited[i][j] = 0;

	ans += maxBlockSize * maxBlockSize;

	return true;
}

1. board를 순회하면서 BFS를 이용해 블록 그룹의 좌표들을 tq에 넣습니다.
2. 이전 블록 그룹보다 크거나, 무지개 블록수가 더 많거나, 행과 열이 작다면
   dq를 tq로 갱신합니다.
3. board순회를 마쳤다면 dq에서 pop하면서 블록을 삭제합니다.

2. 블록 떨어뜨리기

void dropBlock() {
	for (int r = n - 1; r >= 0; r--) {
		for (int c = 0; c < n; c++) {
			// empty or black 블록은 넘어감
			if (board[r][c] < 0) continue; 

			int nr = r + 1;

			// 격자 끝보다 작고 비어있는 동안
			while (nr < n && board[nr][c] == EMPTY) nr++;

                        // 한 칸도 못 내려갔을 때
			if (nr - 1 != r) {
				board[nr - 1][c] = board[r][c];
				board[r][c] = EMPTY;
			}
		}
	}
}

3. 블록 회전하기

void rotateBoard() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			tmp[i][j] = board[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			board[i][j] = tmp[j][n - i - 1];
}

이제 함수들을 순서에 맞게 호출하면 됩니다.

3. 전체 코드

#define RAINBOW 0
#define BLACK -1
#define EMPTY -2
#include <bits/stdc++.h>

using namespace std;

int n, m, ans;
int my[4] = { -1, 0, 1, 0 }, mx[4] = { 0, 1, 0, -1 };
int board[20][20], visited[20][20], tmp[20][20];
queue<pair<int, int>> q, rq, dq, tq;

bool addScoreAndRemoveBlockIfFind() {
	int maxBlockSize = 1, maxRainBowCnt = 0, maxY = -1, maxX = -1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] <= 0 || visited[i][j] == 1) continue;

			int rainBowCnt = 0;
			int blockColor = board[i][j];

			q.push({ i, j });
			tq.push({ i, j });
			visited[i][j] = 1;

			while (!q.empty()) {
				int y = q.front().first;
				int x = q.front().second;

				q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;

					if (board[ny][nx] != RAINBOW && board[ny][nx] != blockColor) continue;

					if (visited[ny][nx] == 1) continue;

					// 무지개일 때 
					if (board[ny][nx] == RAINBOW) {
						// 무지개 카운트 증가
						rainBowCnt++;
						// 무지개 큐에 푸시
						rq.push({ ny, nx });
					}

					q.push({ ny, nx });
					tq.push({ ny, nx });
					visited[ny][nx] = 1;
				}
			}

			int blockSize = tq.size();

			// 블록 크기가 이전 블록보다 클 때
			if (blockSize > maxBlockSize) {
				maxBlockSize = blockSize;
				maxRainBowCnt = rainBowCnt;
				maxY = i;
				maxX = j;
				dq = tq;
			}
			// 블록 크기가 같고 무지개 수가 많을 때
			else if (blockSize == maxBlockSize && rainBowCnt > maxRainBowCnt) {
				maxRainBowCnt = rainBowCnt;
				maxY = i;
				maxX = j;
				dq = tq;
			}
			// 블록 크기가 같고 무지개 수도 같고
			else if (blockSize == maxBlockSize && rainBowCnt == maxRainBowCnt) {
				// 행이 작거나, 행이 같고 열이 작을 때
				if (i > maxY || (i == maxY && j > maxX)) {
					maxY = i;
					maxX = j;
					dq = tq;
				}
			}

			// 무지개 블록은 visited 초기화
			while (!rq.empty()) {
				visited[rq.front().first][rq.front().second] = 0;
				rq.pop();
			}

			while (!tq.empty()) tq.pop();
		}
	}

	// 삭제할 블록이 없을 때
	if (maxBlockSize == 1) return false;

	// 블록 삭제
	while (!dq.empty()) {
		int y = dq.front().first;
		int x = dq.front().second;

		dq.pop();
		board[y][x] = EMPTY;
	}

	// visited 초기화
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visited[i][j] = 0;

	ans += maxBlockSize * maxBlockSize;

	return true;
}

void dropBlock() {
	for (int r = n - 1; r >= 0; r--) {
		for (int c = 0; c < n; c++) {
			// empty or black
			if (board[r][c] < 0) continue; 

			int nr = r + 1;

			// 격자 끝보다 작고 비어있는 동안
			while (nr < n && board[nr][c] == EMPTY) nr++;

			if (nr - 1 != r) {
				board[nr - 1][c] = board[r][c];
				board[r][c] = EMPTY;
			}
		}
	}
}

void rotateBoard() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			tmp[i][j] = board[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			board[i][j] = tmp[j][n - i - 1];
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	while (addScoreAndRemoveBlockIfFind()) {
		dropBlock();
		rotateBoard();
		dropBlock();
	}

	cout << ans;

	return 0;
}