[ BOJ - 21609번 ] 상어 중학교 (C++)

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

 

[ 풀이 방법 ]

1. 크기가 가장 큰 블록 그룹을 찾는 기능

2. 크기가 가장 큰 블록 그룹이 여러개인 경우, 그룹에 포함된 무지개 블록의 수가 가장 많은 그룹을 찾는 기능

  - 아직 탐색하지 않은 일반 블록의 위치를 행과 열이 작은 순서대로 찾고, 찾은 위치에서부터 DFS를 시작해 같은 블록이 들어있거나 무지개 블록이 있는 위치를 방문 처리하며 크기와 무지개 블록 개수를 구한다.

 

  - 구한 크기와 무지개 블록 개수를 비교하여 저장된 최대 블록 그룹 크기와 기준 블록을 갱신한다.

 

  - 이 때, 행과 열이 작은 순서대로 탐색되기 때문에, 탐색한 그룹의 크기와 무지개 블록 개수가 저장된 최대 블록 크기 그룹과 같다면 나중에 탐색된 그룹으로 갱신하여 "기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다."는 조건을 만족시킬 수 있다.

 

  - 무지개 블록은 DFS를 빠져나올때 방문처리를 취소하여 다른 블록 그룹에서도 방문할 수 있게 구현한다.

 

3. 찾아둔 최대 크기 블록 그룹의 기준 블록을 이용하여 해당 블록 그룹을 제거하는 기능

  - BFS를 이용하여 방문할 수 있는 블록을 모두 빈 칸으로 초기화한다.

  - 크기²만큼 점수에 추가한다.

 

4. 격자에 중력을 적용하는 기능

  - 바닥에서부터 위로 올라가며 빈 칸의 개수를 세고, 일반 블록이나 무지개 블록이 있다면 센 빈칸의 개수만큼 바닥으로 내려준다.

  - 검은 블록을 만나면 센 개수를 0으로 초기화한다.

 

5. 격자를 반시계 방향으로 90도 회전하는 기능

  - AUX 배열을 이용

  - 격자의 마지막 열부터 첫 번째 열까지 순서대로 AUX 배열의 첫 번째 행부터 마지막 행까지 옮긴다.

  - 회전 후 중력 적용 기능을 한 번 더 수행한다.

 

6. 더 이상 블록이 제거되지 않을 때까지 위 과정을 반복한 뒤 점수를 출력하는 기능

  - 탐색된 기준 블록이 존재하지 앟ㄴ을 때까지 반복한다.

 

[ 회고 ]

 접근 방법과 구현 계획을 확실히 생각한 뒤 구현하기 위해 노력했고, 구현 단계에서도 계속해서 구현 계획을 검증하며 실수 없이 풀기 위해 노력했다. 그럼에도 예제 입력 2번이 올바른 결과가 나오지 않았지만 생각해둔 구현 계획과 검증 결과를 통해 오류가 발생했을 것 같은 코드를 쉽게 찾을 수 있었고, 디버깅해 문제를 발견할 수 있었다.

 

 방문한 블록을 다시 방문하지 않기 위해 방문 처리할 때, 무지개 블록은 다른 블록 그룹에서도 포함하여 그룹을 형성할 수 있기 때문에 DFS를 빠져나오면서 방문 처리를 취소해 주도록 구현하였는데 이 부분에서 예상치 못한 오류가 발생했다. 하나의 블록 그룹을 탐색할 때에도 무지개 블록이 여러번 포함될 수 있기 때문인데, 이를 해결하기 위해 그룹 별로 사용할 visited 배열과 전체 그룹이 사용할 visited 배열을 나누어 만들고 사용하도록 구현하였고 정답을 맞출 수 있었다.

 

 구현 단계에서 새로 생각한 아이디어나 요구사항에 맞게 정확하게 동작할지 헷갈리는 부분은 다시 계획, 검증 단계로 돌아가 검증해보아야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>

#define RAINBOW 6
#define BLACK -1

using namespace std;

struct Block {
    int x; int y;
    int size; int cnt;
};

int N, M;
vector<vector<int>> board;

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

int maxSize;
Block maxBlock;
int res;

void dfs(int x, int y, vector<vector<bool>>& visited, vector<vector<bool>>& visitedAll, int& size, int& cnt, int num) {
    
    if(visitedAll[x][y]) return;
    
    size++;
    if(board[x][y] == RAINBOW) cnt++;
    visited[x][y] = true;
    visitedAll[x][y] = true;
    
    for(int dir = 0; dir < 4; dir++) {
        int nx = x + dirX[dir];
        int ny = y + dirY[dir];
        
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        
        if(board[nx][ny] == num || board[nx][ny] == RAINBOW) {
            dfs(nx, ny, visited, visitedAll, size, cnt, num);
        }
    }
    
    if(board[x][y] == RAINBOW) visited[x][y] = false;
}

void bfs() {
    
    vector<vector<bool>> visited(N, vector<bool>(N));
    
    queue<pair<int, int>> q;
    q.push({maxBlock.x, maxBlock.y});
    
    visited[maxBlock.x][maxBlock.y] = true;
    
    while(!q.empty()) {
     
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int dir = 0; dir < 4; dir++) {
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if(visited[nx][ny]) continue;
            
            visited[nx][ny] = true;
            
            if(board[nx][ny] == board[maxBlock.x][maxBlock.y] || board[nx][ny] == RAINBOW) {
                board[nx][ny] = 0;
                q.push({nx, ny});
            }
        }
    }
}

void removeBlock() {
    bfs();
    board[maxBlock.x][maxBlock.y] = 0;
    res += pow(maxSize, 2);
}

void gravity() {
    
    for(int j = 0; j < N; j++) {
        int cnt = 0;
        for (int i = N-1; i >= 0; i--) {
            if(board[i][j] == 0) cnt++;
            else if(board[i][j] == BLACK) cnt = 0;
            else {
                if(cnt == 0) continue;
                board[i+cnt][j] = board[i][j];
                board[i][j] = 0;
            }
        }
    }
}

void rotate() {
    vector<vector<int>> aux(N, vector<int>(N));
    
    
    for(int i = 0, k = N-1; i < N && k >= 0; i++, k--) {
        for (int j = 0; j < N; j++) {
            aux[i][j] = board[j][k];
        }
    }

    board.swap(aux);
    vector<vector<int>>().swap(aux);
}

void solve() {
    
    do {
        maxSize = 0;
        maxBlock = {0, 0, 0, 0};
        vector<vector<bool>> visited(N, vector<bool>(N));
        
        // 제거할 블록 그룹 탐색
        for(int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(board[i][j] == RAINBOW || board[i][j] == BLACK || board[i][j] == 0) continue;
                if(!visited[i][j]) {
                    int size = 0;
                    int cnt = 0;
                    
                    vector<vector<bool>> visitedAll(N, vector<bool>(N));
                    
                    dfs(i, j, visited, visitedAll, size, cnt, board[i][j]);
                    
                    vector<vector<bool>>().swap(visitedAll);
                    
                    if(size > maxSize && size >= 2) {
                        maxSize = size;
                        maxBlock = {i, j, size, cnt};
                    } else if(size == maxSize && size >= 2) {
                        if(maxBlock.cnt <= cnt) {
                            maxBlock = {i, j, size, cnt};
                        }
                    }
                }
            }
        }

        // 탐색된 블록 그룹 제거
        removeBlock();
        
        // 중력 적용
        gravity();
        
        // 반시계 방향 90도 회전
        rotate();
        
        gravity();
        
        vector<vector<bool>>().swap(visited);
    } while(maxSize >= 2);
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    
    board.resize(N, vector<int>(N));
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if(!board[i][j]) board[i][j] = RAINBOW;
        }
    }
    
    solve();
    
    cout << res << '\n';
    
    return 0;
}