상어 중학교 (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;
}
board
를 순회하면서BFS
를 이용해 블록 그룹의 좌표들을tq
에 넣습니다.- 이전 블록 그룹보다 크거나, 무지개 블록수가 더 많거나, 행과 열이 작다면
dq
를tq
로 갱신합니다. 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;
}
Author And Source
이 문제에 관하여(상어 중학교 (21609)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-상어-중학교-21609저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)