[BaekJoon/C++] 21609번 상어 중학교

17822번 백준 - 상어 중학교

 

문제 링크: https://www.acmicpc.net/problem/21609

 

 

 

문제를 풀고 한참동안이나 어디서 코드가 틀린지를 못 찾았는데 질문 게시판에 가서 답을 얻을 수 있었다. 

내가 놓쳤던 부분은 아래와 같다! 

 

1. 무지개 방문처리 해제했는지 확인하기

2. 기준 블록을 잡을 때 행과 열이 가장 작은 걸로 잡음

 

코드:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
int arr[21][21];
bool visited[21][21];
int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { -1, 1, 0, 0 };
int totalScore = 0;

struct BlockGroup {
    int r;
    int c;
    int size;
    int rainbowCnt;
    vector<pair<int, int>> blocks;
};

// 블록 그룹을 비교하여 정렬할 때 사용할 함수
bool cmp(const BlockGroup& a, const BlockGroup& b) {
    if (a.size != b.size) return a.size > b.size;
    if (a.rainbowCnt != b.rainbowCnt) return a.rainbowCnt > b.rainbowCnt;
    if (a.r != b.r) return a.r > b.r;
    return a.c > b.c;
}

// 블록 그룹 내에서 기준 블록을 정하는 비교 함수
bool cmpBlocks(const pair<int, int>& a, const pair<int, int>& b) {
    if (arr[a.first][a.second] != 0 && arr[b.first][b.second] != 0) {
        return a < b;
    }
    if (arr[a.first][a.second] == 0) {
        return false;
    }
    if (arr[b.first][b.second] == 0) {
        return true;
    }
    return a < b;
}

bool isArea(int r, int c) {
    return r >= 0 && r < N && c >= 0 && c < N;
}

int findBlock() {
    memset(visited, 0, sizeof(visited));
    vector<BlockGroup> groups;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j] && arr[i][j] > 0) {
                int color = arr[i][j];
                queue<pair<int, int>> q;
                vector<pair<int, int>> blocks;
                vector<pair<int, int>> rainbowBlocks;
                int rainbowCnt = 0;

                q.push(make_pair(i, j));
                visited[i][j] = true;
                blocks.push_back(make_pair(i, j));

                while (!q.empty()) {
                    int r = q.front().first;
                    int c = q.front().second;
                    q.pop();

                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d];
                        int nc = c + dc[d];

                        if (isArea(nr, nc) && !visited[nr][nc] && (arr[nr][nc] == color || arr[nr][nc] == 0)) {
                            q.push(make_pair(nr, nc));
                            visited[nr][nc] = true;
                            blocks.push_back(make_pair(nr, nc));
                            if (arr[nr][nc] == 0) {
                                rainbowCnt++;
                                rainbowBlocks.push_back(make_pair(nr, nc));
                            }
                        }
                    }
                }

                for (int k = 0; k < rainbowBlocks.size(); k++) {
                    int rr = rainbowBlocks[k].first;
                    int cc = rainbowBlocks[k].second;
                    visited[rr][cc] = false;
                }

                if (blocks.size() >= 2) {
                    sort(blocks.begin(), blocks.end(), cmpBlocks);
                    BlockGroup bg;
                    bg.r = blocks[0].first;
                    bg.c = blocks[0].second;
                    bg.size = blocks.size();
                    bg.rainbowCnt = rainbowCnt;
                    bg.blocks = blocks;
                    groups.push_back(bg);
                }
            }
        }
    }

    if (groups.empty()) return 0;

    sort(groups.begin(), groups.end(), cmp);
    BlockGroup largest = groups[0];
    totalScore += largest.size * largest.size;

    for (int k = 0; k < largest.blocks.size(); k++) {
        int rr = largest.blocks[k].first;
        int cc = largest.blocks[k].second;
        arr[rr][cc] = -2;  // 제거 표시
    }

    return largest.size * largest.size;
}

void applyGravity() {
    for (int c = 0; c < N; c++) {
        for (int r = N - 1; r >= 0; r--) {
            if (arr[r][c] > -1) { // 빈 공간 (-2) / 검은색 블록 (-1)이 아닌 경우
                int nr = r;
                while (nr + 1 < N && arr[nr + 1][c] == -2) {
                    arr[nr + 1][c] = arr[nr][c];
                    arr[nr][c] = -2;
                    nr++;
                }
            }
        }
    }
}

void rotateBlock() {
    int tmp[21][21];
    memcpy(tmp, arr, sizeof(arr));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[N - 1 - j][i] = tmp[i][j];
        }
    }
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }

    int result = 0;
    while (true) {
        int score = findBlock();
        if (score == 0) break;
        result += score;
        applyGravity();
        rotateBlock();
        applyGravity();
    }

    cout << result << "\n";
    return 0;
}