백준 21609: 상어중학교(c++, 구현 & BFS)

사용 언어	티어	시간 제한	메모리 제한
c++		1초	1024MB

 

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

21609번: 상어 중학교

 

#0 문제

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.격자에 중력이 작용한다.격자가 90도 반시계 방향으로 회전한다.다시 격자에 중력이 작용한다.
격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

#1 입력

첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.

 

#2 접근

• 전형적인 삼성 코딩테스트 구현 문제이다. BFS를 이용해야하고, 여러 조건들을 고려해야하므로 생각보다 까다롭다.
• 4번 정도 시도 후에 겨우 맞혔는데, 기준 블럭과, 그룹의 우선순위를 잘 고려해서 구현해야함에 유의해야한다.
• 기준 블럭은 무지개 블럭이 될 수 없음에 유의하고, 여러 블록 그룹이 있을 땐 우선순위 처리를 정확하게 해주어야 한다.
• 회전하는 것은 행렬의 회전을 이용하면 되고, 중력 작용은 큐나 벡터를 사용해서 구현하면 된다.

#3 풀이

• 우선 반시계 방향으로의 90도 회전은 [x, y] -> [y, n - 1 - x] 임을 이용해서 구현하면 된다. 굳이 외울 필요는 없고, 기준점을 바꾸어서 조금만 생각해보면 떠올릴 수 있다.
• 중력작용은 검은색 블록과 범위 밖의 index를 기준으로 적용시켰다. 검은색 블록과 범위 밖의 index를 같은 것으로 취급한다.(둘 다 검은색 블록으로 부르겠다.)
  • 검은색 블록을 만나기 전까지 모든 블록들을 큐에 넣는다. (무지개 블록과 일반 블록)
  • 검은색 블록을 만나면, 이전 검은색 블록의 index ~ 현재 검은색 블록의 index에 중력작용을 적용시키는데, 큐에 넣어둔 내용을 하나씩 빼서 각각 index에 넣어주면 되고, 원래 있던 곳은 빈칸처리해주면 된다.
• 크기가 가장 큰 블록 그룹을 찾는데, 이러한 것이 여러 개이면 무지개 블록이 가장 많은 블록, 이러한 것도 여러개면 기준 행이 가장 큰 것, 이 역시 여러 개면 기준 열이 가장 큰 것을 선택한다.
  • 우선 전체 board의 각각 좌표에 대해 BFS로 탐색해준다.
  • 탐색의 시작점은 일반블록부터 한다. 검은색 블록은 포함될 수 없으므로 당연히 시작점이 될 수 없고, 무지개 블록으로 시작하면 앞으로 보아야할 색깔을 특정할 수 없기 때문에 시작점으로 삼지 않는다. 어짜피 일반 블록으로 시작하면 무지개 블록은 포함될 것이므로 상관없다.
  • 무지개 블록은 공유될 수 있으므로, 새로운 BFS 탐색이 있을 때마다 무지개 블록은 초기화해주어야 한다.
  • 우선순위를 위한 cnt, 무지개 블록의 개수, 기준블록의 행과 열을 선언해준다.
  • 탐색중에는 기준 블럭을 갱신해준다. 행과 열이 가장 작은 것이 기준 블럭이 되도록 구현하면 된다.
  • 하나의 블록 그룹에 대해 탐색을 마치면, 최댓값을 갱신해준다. 위에서 말했던 무지개 블럭과, 기준 블럭 등의 우선순위에 맞게 갱신해주면 된다. 이 부분에서 깔끔하게 처리하지 못하면 계속 틀렸습니다를 맞이할 것이다.
  • 최댓값이 1이하일 경우엔 결국 블록 그룹을 찾지 못한 것이기 때문에 종료 플래그를 설정해준다.
  • 1보다 클 경우엔 블록 그룹을 찾았기 때문에, 기준 블럭을 시작점으로 하여 다시 BFS 탐색을 시작하며, 해당하는 모든 블록들을 지워주면 된다.
• 구현해둔 회전, 중력, 블록 그룹 찾기를 종료 플래그가 생길 때까지 반복하면 된다.

 

#4 코드

/*
21609 상어 중학교
구현 & BFS
*/

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;


typedef pair<int, int> Pos;



int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};


int n, m;
int score;
int finish;


// 회전
vector<vector<int>> rotate(vector<vector<int>> board) {
    vector<vector<int>> new_board(n, vector<int>(n, 0));

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

    return new_board;
}




// 중력
vector<vector<int>> gravity(vector<vector<int>> board) {
    // 검은 블록엔 중력이 작용하지 않음
    // 밑에서부터 올라가되 검은 블록을 만나면 break;

    for (int j = 0; j < n; ++j) {
        // -2인 칸으로 떨어트려야함! -2인 칸의 개수를 세고 떨어트리면 된다? 벡터를 쓸까?
        // 검은색을 만나기 전까지 모든 것들을 큐에 넣자!
        // 그리고 이전 검은색 index에서 현재 검은색 index까지 내용을 큐에서 pop하면서 바꿔주자!
        // outofindex도 검은색 취급!
        queue<Pos> q;
        int black_idx = n;
        int prev_black_idx = n;

        for (int i = n - 1; i >= 0; --i) {
            if (board[i][j] == -1) {
                black_idx = i;
                for (int k = prev_black_idx - 1; k > black_idx; --k) {
                    if (q.empty()) break;
                    board[k][j] = q.front().first;
                    if (q.front().second != k) board[q.front().second][j] = -2;
                    q.pop();
                }
                prev_black_idx = black_idx;
                q = {};
            } else {
                if (board[i][j] >= 0) {
                    q.push({board[i][j], i});
                }
            }

            if (i == 0) {
                for (int k = prev_black_idx - 1; k > 0; --k) {
                    if (q.empty()) break;
                    board[k][j] = q.front().first;
                    if (q.front().second != k) board[q.front().second][j] = -2;
                    q.pop();
                }
            }
        }
    }


    return board;
}







// 큰 그룹 찾기
vector<vector<int>> find_large(vector<vector<int>> board) {
    // 크기가 가장 큰 블록 그룹을 찾는데, 여러개면 무지개 블록이 가장 많은 블록, 그것도 여러개면 행이 가장 큰 것, 그것도 여러개면 열이 가장 큰것
    // cnt > rainbow > row > col

    // bfs로 찾기
    vector<vector<int>> visited(n, vector<int>(n, 0));
    int max_cnt = 0;
    int max_row = -1;
    int max_col = -1;
    int prev_rainbow = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // bfs 여러번 돌리기
            // 무지게 == 0, 검은색 == -1, 일반은 1이상

            if (board[i][j] == 0 || board[i][j] == -2 || board[i][j] == -1) {
                // 탐색의 시작은 무조건 일반블록부터
                continue;
            }
            
            for (int k = 0; k < n; ++k) {
                for (int s = 0; s < n; ++s) {
                    if (board[k][s] == 0) visited[k][s] = 0;
                }
            }

            queue<Pos> q;
            visited[i][j] = 1;
            q.push({i, j});

            // 초기값 배정
            int cnt = 0;
            int rainbow = 0;
            int color = board[i][j];
            int std_row = i;
            int std_col = j;

            while (!q.empty()) {
                Pos node = q.front();
                q.pop();

                cnt++;
                int x = node.first;
                int y = node.second;

                //기준 블록 찾아야함
                if (board[x][y] != 0) {
                    if (x < std_row) {
                        std_row = x;
                        std_col = y;
                    } else if (x == std_row) {
                        if (y < std_col) {
                            std_col = y;
                        }
                    }
                }


                for (int k = 0; k < 4; ++k) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];

                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (!visited[nx][ny]) {
                            if (board[nx][ny] == color) {
                                q.push({nx, ny});
                                visited[nx][ny] = 1;
                            }
                            if (board[nx][ny] == 0) {
                                q.push({nx, ny});
                                visited[nx][ny] = 1;
                                rainbow++;
                            }
                        }
                    }
                }
            }
            

            // 우선순위 판단해서 i, j 뽑아내기
            if (cnt > max_cnt) {
                max_row = std_row;
                max_col = std_col;
                prev_rainbow = rainbow;
                max_cnt = cnt;
            } else if (cnt == max_cnt) {
                if (rainbow > prev_rainbow) {
                    prev_rainbow = rainbow;
                    max_row = std_row;
                    max_col = std_col;
                } else if (rainbow == prev_rainbow) {
                    if (max_row < std_row) {
                        max_row = std_row;
                        max_col = std_col;
                    } else if (max_row == std_row) {
                        if (max_col < std_col) {
                            max_col = std_col;
                        }
                    }
                }
            }
        }
    }

    if (max_cnt <= 1) {
        max_cnt = 0;
        finish = 1;
    } else {
        //이제 최우선순위의 기준블럭 i, j를 찾아냄!
        score += max_cnt * max_cnt;
        // 다시 bfs해서 지워버리기! 이때는 -2로 바꿔주자!

        vector<vector<int>> visited2(n, vector<int>(n, 0));
        queue<Pos> q2;
        visited2[max_row][max_col] = 1;
        q2.push({max_row, max_col});

        int cnt = 0;
        int color = board[max_row][max_col];


        while (!q2.empty()) {
            Pos node = q2.front();
            q2.pop();

            int x = node.first;
            int y = node.second;
            
            // 빈칸처리해주기
            board[x][y] = -2;

            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (!visited2[nx][ny]) {
                        if (board[nx][ny] == color || board[nx][ny] == 0) {
                            q2.push({nx, ny});
                            visited2[nx][ny] = 1;
                        }
                    }
                }
            }
        }
    }


    return board;
}


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

    cin >> n >> m;



    vector<vector<int>> board(n, vector<int>(n, 0));

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

    while (!finish) {
        board = find_large(board);
        board = gravity(board);
        board = rotate(board);
        board = gravity(board);
    }
    

    cout << score;

    return 0;
}