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

2021년 삼성 코딩테스트 2번 문제였다.
정말 호흡이 길었던 빡센 구현 문제여서 풀었을 때 도파민이 엄청났다..

문제 및 입출력

중간 그림은 생략하였다.

정보량이 정말 많아서 세심하게 정리하지 않으면 뻘짓으로 가득해지는 문제다.
문제에서 추출할 수 있는 정보는 다음과 같다.

• 특정 블록의 상하좌우 블록을 인접한 블록이라고 한다.
• 블록 그룹은 적어도 하나의 일반 블록(1~M번)이 존재해야 하고, 적어도 2개 이상의 블록으로 구성되어야 하며, 그룹 내부 일반 블록의 색은 모두 같아야 한다.
• 그룹 내에선 어떤 그룹 구성 블록으로 이동할 수 있어야 한다.
• -1은 검은 블록, 0은 무지개 블록이다.
• 비어있는 블록임을 표현할 번호가 필요하다. (-2로 처리)
• 무지개 블록은 어떤 그룹 블록이든 포함될 수 있다.
• 블록 그룹은 기준 블록을 가지며, 기준 블록은 무지개색이 아니다.
• 우선순위가 가장 높은 블록 그룹을 찾아 제거하고 그룹의 크기^2를 계산한다.
• 우선순위는 크기 내림차순, 무지개 개수 내림차순, 기준블록 행-열 오름차순이다.
• 제거 후 중력으로 인해 블록들이 바닥(마지막 행 방향)으로 떨어진다.
• 검은 블록은 중력이 적용되지 않으며, 일종의 받침대 역할을 수행한다.
• 회전을 통해 전체 블록이 90도 반시계로 회전한다.
• 회전 후 다시 중력이 적용된다.
• 이 사이클이 종료 전까지 반복된다.
• 종료조건: 블록 그룹이 아예 없거나, 현재 사이클에 크기가 2 이상인 블록 그룹이 존재하지 않는 경우

이 모든 정보를 쥐고 해결 과정으로 들어가야 한다.
거의 비문학 수준이다,,

해결 과정

문제에서 제시한 대로 오토플레이를 구성하는 하나의 Cycle는 다음과 같다.

• 각 그룹 블록별 BFS
• BFS의 결과로 생성된 그룹 블록 중 가장 우선순위가 높은 블록 선택
• 해당 블록을 제거하고 블록의 크기^2 계산
• 중력 적용
• 90도 반시계 회전
• 중력 적용

BFS, 우선순위 산출, 블록 그룹 제거, 중력, 회전
크게 6가지로 과정을 분리해서 하나씩 구현하였다.

BFS

우선순위 산출에 활용하기 위해 그룹 크기와 무지개블록 개수를 반환하도록 했다.

pair<int, int> bfs(int sx, int sy){
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));
    int cnt = 1;
    int rainbow = 0;
    int color = map[sx][sy];

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(visited[nx][ny] || map[nx][ny] == -1) continue;
            if(map[nx][ny] == 0 || map[nx][ny] == color){
                if(map[nx][ny] == 0) rainbow++;
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                cnt++;
            }
        }
    }
    return make_pair(cnt, rainbow); // 그룹 크기, 무지개 개수
}

참고로 매 BFS 전 모든 무지개 블록의 방문 여부를 다시 False로 초기화주어야 한다.
무지개 블록은 모든 그룹이 사용할 수 있는 공공재이기에, 앞 그룹이 사용했다는 이유로 바로 뒷 그룹이 사용하지 못하는 불상사가 발생할 수 있기 때문이다.

이 문제를 파악하는 게 중력 구현과 더불어 가장 오랜 시간이 걸렸다.

우선순위 산출

bool cmp(pair<pair<int, int>, pair<int, int> > p1, pair<pair<int, int>, pair<int, int> > p2){ // 문제 요구에 따른 정렬
    if(p1.first.first == p2.first.first){
        if(p1.first.second == p2.first.second){
            if(p1.second.first == p2.second.first){
                return p1.second.second > p2.second.second;
            }
            return p1.second.first > p2.second.first;
        }
        return p1.first.second > p2.first.second;
    }
    return p1.first.first > p2.first.first;
}

2쌍의 pair로 구성된 벡터를 통해 (그룹크기, 그룹 내 무지개 개수, 기준블록 행번호, 기준블록 열번호)를 바탕으로 정렬을 수행하여 가장 우선순위가 높은 블록 그룹을 선택 및 제거하였다.

블록 그룹 제거

이 그룹에 속한 모든 블록을 다 치우고 빈 블록으로 채워야 하기 때문에 이 역시 BFS가 필요했다. 빈 블록은 -2로 표현하였다. (0이 무지개블록이므로)

int deleteblock(int sx, int sy){
    memset(visited, false, sizeof(visited));
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));
    int cnt = 1;
    int color = map[sx][sy];
    copys[sx][sy] = -2; // 빈 블록

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(visited[nx][ny] || map[nx][ny] == -1) continue;
            if(map[nx][ny] == 0 || map[nx][ny] == color){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                copys[nx][ny] = -2;
                cnt++;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = copys[i][j]; // 빈 블록 업데이트
        }
    }
    return cnt*cnt;
}

참고로 복사본 배열을 사용하지 않고 바로바로 좌표를 빈 블록 -2로 수정하면 다음 연산이 이 영향을 받아 잘못된 결과가 나타난다.

이해하기 어려우면 이 문제를 먼저 풀고 오는 것을 권한다.

중력

무지개 블록 이슈와 더불어 사실상 이 문제의 승부처였다.
회전도 아닌 중력..이라는 낯선 연산을 -1이라는 받침대(?)와 함께 구현해야 했다.

바닥으로부터 위로 올라오며 받침대인지, 빈 공간인지, 블록인지를 판정한 후,

• 빈 공간(-2) -> 아무 일 없음
• 받침대(-1) -> 빈 공간이 나오기 전까지 계속 바닥 상승,
  만약 인덱스가 지붕(0)을 뚫으면 해당 열은 중력 연산 종료
• 블록(0~M) -> 블록과 현재 바닥을 의미하는 빈 블록을 Swap하고 바닥 한칸 상승

void gravity(){ // 중력
    for(int j=0; j<n; j++){
        int nextf = n-1; // 바닥 설정
        for(int i=n-1; i>=0; i--){
            if(map[i][j] == -2) { // 빈공간 -> 아무일도 없음
                continue;
            } else if(map[i][j] == -1){ // 받침대
                nextf = i;
                while(map[nextf][j] != -2) { // 빈공간 나오기 전까지 쭉 올라감
                    nextf--;
                    if(nextf < 0){ // 지붕 뚫을 시 종료
                        i = -1;
                        break;
                    }
                }
                i = nextf; // 받침대 위 어딘가의 새로운 바닥 정의
            } else {
                swap(map[nextf][j], map[i][j]); // 블록이 바닥으로 이동
                nextf--; // 바닥 1칸 상승
            }
        }
    }
}

Swap을 해도 되는가? 라는 고민이 있었지만, 받침대를 감지할 시 바닥을 재정의하는 부분 덕분에 문제 없이 처리가 가능하다.

회전

void rotate(){ // 90도 반시계 회전
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            copys[i][j] = map[j][n-1-i];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = copys[i][j];
        }
    }
}

복사본 배열을 통해 회전을 구현한 후 원본 배열에 반영하였다.

소스 코드

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

using namespace std;
int n, m;
int copys[401][401]; // 복사본
int map[401][401]; // -2는 공백, -1은 검정, 0은 무지개
bool visited[401][401];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void input(){ // 입력
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
}

void makecopy(){ // 복사본 배열 초기화
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            copys[i][j] = map[i][j];
        }
    }
}

bool cmp(pair<pair<int, int>, pair<int, int> > p1, pair<pair<int, int>, pair<int, int> > p2){ // 문제 요구에 따른 정렬
    if(p1.first.first == p2.first.first){
        if(p1.first.second == p2.first.second){
            if(p1.second.first == p2.second.first){
                return p1.second.second > p2.second.second;
            }
            return p1.second.first > p2.second.first;
        }
        return p1.first.second > p2.first.second;
    }
    return p1.first.first > p2.first.first;
}

pair<int, int> bfs(int sx, int sy){
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));
    int cnt = 1;
    int rainbow = 0;
    int color = map[sx][sy];

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(visited[nx][ny] || map[nx][ny] == -1) continue;
            if(map[nx][ny] == 0 || map[nx][ny] == color){
                if(map[nx][ny] == 0) rainbow++;
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                cnt++;
            }
        }
    }
    return make_pair(cnt, rainbow); // 그룹 크기, 무지개 개수
}

int deleteblock(int sx, int sy){
    memset(visited, false, sizeof(visited));
    queue<pair<int, int> > q;
    visited[sx][sy] = true;
    q.push(make_pair(sx, sy));
    int cnt = 1;
    int color = map[sx][sy];
    copys[sx][sy] = -2; // 빈 블록

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

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if(visited[nx][ny] || map[nx][ny] == -1) continue;
            if(map[nx][ny] == 0 || map[nx][ny] == color){
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
                copys[nx][ny] = -2;
                cnt++;
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = copys[i][j]; // 빈 블록 업데이트
        }
    }
    return cnt*cnt;
}

void gravity(){ // 중력
    for(int j=0; j<n; j++){
        int nextf = n-1; // 바닥
        for(int i=n-1; i>=0; i--){
            if(map[i][j] == -2) {
                continue;
            } else if(map[i][j] == -1){
                nextf = i;
                while(map[nextf][j] != -2) {
                    nextf--;
                    if(nextf < 0){
                        i = -1;
                        break;
                    }
                }
                i = nextf;
            } else {
                swap(map[nextf][j], map[i][j]);
                nextf--;
            }
        }
    }
}

void rotate(){ // 90도 반시계 회전
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            copys[i][j] = map[j][n-1-i];
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            map[i][j] = copys[i][j];
        }
    }
}

void zeroreset(){ // 무지개 블록은 모든 그룹들이 쓸 수 있어야 하므로 매 탐색마다 초기화해줘야함
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j] && map[i][j] == 0) visited[i][j] = false;
        }
    }
}

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

    input();
    int answer = 0;
    while(1){
        memset(visited, false, sizeof(visited));
        makecopy();
        vector<pair<pair<int, int>, pair<int, int> > > v;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(!visited[i][j] && map[i][j] >= 1){
                    pair<int, int> blocks = bfs(i, j);
                    v.push_back(make_pair(blocks, make_pair(i, j)));
                    zeroreset();
                }
            }
        }
        if(v.empty()) break; // 비었으면 종료
        sort(v.begin(), v.end(), cmp);
        if(v[0].first.first < 2) break; // 젤 큰 그룹 크기가 2 미만이면 종료
        answer += deleteblock(v[0].second.first, v[0].second.second);
        gravity(); // 중력
        rotate(); // 90도 반시계 회전
        gravity(); // 중력
    }
    cout << answer;
    return 0;
}

교훈

• 코드를 치기 전에 내가 놓치면 안 되는 정보를 미리 정리해두고 시작하자. 숨겨진 정보로 인해 시간을 너무 낭비했다.
• 2차원 배열을 활용한 회전 등의 변칙적인 연산은 여러 문제로 익숙해져야 실전에서 빠르게 처리할 수 있다.