[백준 21609] 상어중학교 (C++ 풀이)

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

21609번: 상어 중학교

---

이 문제는 골드2 레벨의 구현 문제입니다. 

문제 풀이에 주의할 사항은 다음과 같습니다.

1. 크기가 가장 큰 블록을 찾을 때 bfs 알고리즘을 이용하는데, 이 때 무지개 블록은 중복으로 사용해야 합니다.
2. 중력이 작용하는 경우 검정 블록(-1)을 만나면 거기서 블록이 멈춰야합니다

풀이

---

알고리즘 풀이 순서는 다음과 같습니다. 

1. 가장 큰 블록 그룹 탐색 - find_largest_block_group() 
2. 가장 큰 블록 그룹 삭제 - delete_best_block_group() 
3. 중력 작용 - work_gravity()
4. 배열 90도 회전 - rotate90()
5. 중력 작용 - work_gravity()

전역변수  및 메인 함수

풀이에 사용한 전역 변수 및 메인함수는 다음과 같습니다.

#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int N, M;
vector<vector<int> > board;
enum {
    RAINBOW = 0, BLACK = -1, EMPTY = -2
};
const int dy[] = { 0, 1, 0,  -1 };
const int dx[] = { 1, 0, -1, 0 };
int score = 0;// 획득한 점수
vector<pair<int, int> > best_blocks; // 가장 적합한 블록
int best_rainbows; // 가장 적합한 블록의 무지개 블록 수
int best_start_y; // 가장 적합한 블록의 시작 Y 좌표
int best_start_x; // 가장 적합한 블록의 시작 X 좌표
vector<vector<bool> > used; // 방문 기록용 벡터(BFS에서 사용)
 
 
...
 
 
int main() {
    cin >> N >> M;
    // 입력
    board = vector<vector<int> >(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> board[i][j];
    // 풀이
    while(find_largest_block_group()){ // 가장 큰 블록이 존재하는 동안 반복
        delete_best_block_group(); // 가장 큰 블록 제거 및 점수 획득
        work_gravity(); // 중력 작용
        rotate90(); // 90도 회전
        work_gravity(); // 중력 작용
    }
    cout << score << endl;
}

 

함수 하나하나 살펴보도록 하겠습니다.

1. 가장 큰 블록 그룹 탐색 - find_largest_block_group() 

bool compare_block_groups(vector<pair<int, int>> blocks, int rainbows, int start_y, int start_x) {
    // * 블록 비교 방법에 따라 블록 비교
    // 크기가 가장 큰 블록 그룹을 찾는다. 
    // 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
    // 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
 
    if (best_blocks.size() < blocks.size()) {
        return true;
    }
    else if (best_blocks.size() == blocks.size()) {
        if (best_rainbows < rainbows)
            return true;
        else if (best_rainbows == rainbows) {
            if (best_start_y < start_y) {
                return true;
            }
            else if (best_start_y == start_y) {
                if (best_start_x < start_x)
                    return true;
            }
        }
    }
    return false;
}
 
void bfs(int y, int x, int block_number) {
    // bfs를 이용하여 가장 큰 블록그룹 탐색
 
    queue<pair<int, int>> q; // Queue
    vector<pair<int, int>> rainbows; // 무지개 블록 좌표 저장 용도
    vector<pair<int, int>> blocks; // 블록 그룹 좌표 저장 용도
 
    q.push(make_pair(y, x));
    blocks.push_back(make_pair(y, x));
    used[y][x] = true;
 
    while (!q.empty()) {
        int sy = q.front().first;
        int sx = q.front().second;
        q.pop();
 
        // 4방향 탐색
        for (int d = 0; d < 4; ++d) { 
            int ny = sy + dy[d];
            int nx = sx + dx[d];
 
            if (ny < 0 || nx < 0 || ny >= N || nx >= N || used[ny][nx]) continue; // 범위를 벗어났거나 사용한 경우
            else if (board[ny][nx] == block_number || board[ny][nx] == RAINBOW) { // 블록 번호가 같거나 무지개 블록인 경우
                blocks.push_back(make_pair(ny, nx));
                q.push(make_pair(ny, nx));
                used[ny][nx] = true;
                if (board[ny][nx] == RAINBOW) // 무지개 블록은 무지개 블록 리스트에 추가
                    rainbows.push_back(make_pair(ny, nx));
            }
        }
    }
    if (compare_block_groups(blocks, rainbows.size(), y, x)) { 
        // 블록 비교 결과 현재 탐색한 블록이 우세한 경우
        best_blocks = blocks;
        best_rainbows = rainbows.size();
        best_start_y = y;
        best_start_x = x;
    }
    
    // 무지개 블록은 중복해서 사용하므로 무지개 블록 좌표들의 used(사용 여부)를 false로 변경
    for (int i = 0; i < rainbows.size(); i++){
        int sy = rainbows[i].first;
        int sx = rainbows[i].second;
        used[sy][sx] = false;
    }
}
bool find_largest_block_group() {
    // 가장 큰 블록 그룹을 찾는 함수
 
    used = vector<vector<bool> >(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!used[i][j] && board[i][j] > 0) // 사용하지 않았거나, 일반 블록인 경우(>0)
                bfs(i, j, board[i][j]);
        }
    }
    // 가장 큰 블록 그룹의 크기가 1보다 큰 경우 True, 같거나 작은 경우 False
    // 알고리즘 종료 조건 : 가장 큰 블록 그룹 크기가 2보다 작은 경우
    return best_blocks.size() > 1; 
}

 

find_largest_block_group() 함수에서 가장 큰 블록 그룹을 찾습니다. 가장 큰 블록의 크기가 2보다 작은 경우 False를 반환하며 메인함수에서 알고리즘이 중단되도록 합니다.

함수 내부에서는 각 좌표에 대해 bfs() 함수를 호출하여 각 좌표의 블록 그룹을 찾습니다. 이 때 무지개 좌표는 중복되야 하므로 bfs 탐색 후 무지개 좌표들의 사용 여부를 false로 변경합니다.

compare_block_groups() 함수는 현재 가장 큰 블록 그룹과 탐색한 블록 그룹을 비교하여 탐색한 블록 그룹이 더 큰 블록 그룹인 경우 true를 반환합니다.

2. 가장 큰 블록 그룹 삭제 - delete_best_block_group() 

void delete_best_block_group() {
    // 가장 큰 블록 그룹 삭제 및 점수 획득
    for (int i = 0; i < best_blocks.size(); ++i) {
        int y = best_blocks[i].first;
        int x = best_blocks[i].second;
        board[y][x] = EMPTY;
    }
    score += best_blocks.size() * best_blocks.size();
    
    // 블록 그룹을 사용했으므로, 가장 큰 블록 그룹 정보 초기화
    best_blocks.clear();
    best_rainbows = best_start_y = best_start_x = 0;
}

 

delete_best_block_group() 함수에서 1번에서 찾은 블록 그룹의 좌표들을 모두 EMPTY로 변경합니다.

블록 그룹의 사이즈의 제곱 만큼 점수를 획득하고, 블록 그룹의 정보를 모두 초기화 합니다.

3. 중력 작용 - work_gravity()

void work_gravity() {
    // 중력 작용
    for (int i = N - 2; i >= 0; --i) { // N-2부터 0까지 탐색(마지막 행으로부터 첫번째의 행부터 줄여가며)
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == EMPTY || board[i][j] == BLACK) continue; // 비어있거나 검정 블록인 경우 continue
 
            // 현재행(i)의 다음행 부터 탐색하여 EMPTY가 아닐때 가지 행간 블록데이터 교환
            for (int k = i + 1; k < N; ++k) {
                if (board[k][j] == EMPTY) { // (k, j)가 빈 좌표인 경우
                    board[k][j] = board[k-1][j]; // (k, j)에 (k-1, j)의 값 전달
                    board[k-1][j] = EMPTY; // (k-1, j)는 EMPTY로 변경
                }
                else // (k, j)가 빈 좌표가 아닌 경우
                    break;
            }
        }
    }
}

 

배열의 N-2부터 시작해서 빈 좌표이거나 검정 블록이 아닌 경우 해당 블록을 밑으로 내립니다. 위쪽 행 부터 시작하지 않는 이유는 아래 블록들이 먼저 내려가야 위쪽 블록도 내려가지기 때문입니다.

밑으로 내리는 과정은 현재 블록의 행의 다음 행부터 EMPTY 좌표가 아닐때까지 좌표간 교환을 해주면 됩니다. (8~12번 줄)

4. 배열 90도 회전 - rotate90()

void rotate90() {
    // 배열을 90도회전 시킴
    vector<vector<int >> new_board = vector<vector<int>>(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            new_board[i][j] = board[j][N - i - 1];
        }
    }
    board = new_board;
}
 

 

배열을 90도 회전 시킵니다.  설명은 생략하겠습니다.

5. 중력 작용 - work_gravity()

3번의 함수를 다시 한번 호출합니다.

 

전체 소스 코드

---

#include <vector>
#include <iostream>
#include <queue>
 
using namespace std;
int N, M;
vector<vector<int> > board;
enum {
    RAINBOW = 0, BLACK = -1, EMPTY = -2
};
const int dy[] = { 0, 1, 0,  -1 };
const int dx[] = { 1, 0, -1, 0 };
 
int score = 0;// 획득한 점수
vector<pair<int, int> > best_blocks; // 가장 적합한 블록
int best_rainbows; // 가장 적합한 블록의 무지개 블록 수
int best_start_y; // 가장 적합한 블록의 시작 Y 좌표
int best_start_x; // 가장 적합한 블록의 시작 X 좌표
 
vector<vector<bool> > used; // 방문 기록용 벡터(BFS에서 사용)
 
void pboard() {
    for (size_t i = 0; i < board.size(); i++)
    {
        for (size_t j = 0; j < board.size(); j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
bool compare_block_groups(vector<pair<int, int>> blocks, int rainbows, int start_y, int start_x) {
    // * 블록 비교 방법에 따라 블록 비교
    // 크기가 가장 큰 블록 그룹을 찾는다. 
    // 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
    // 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
 
    if (best_blocks.size() < blocks.size()) {
        return true;
    }
    else if (best_blocks.size() == blocks.size()) {
        if (best_rainbows < rainbows)
            return true;
        else if (best_rainbows == rainbows) {
            if (best_start_y < start_y) {
                return true;
            }
            else if (best_start_y == start_y) {
                if (best_start_x < start_x)
                    return true;
            }
        }
    }
    return false;
}
void bfs(int y, int x, int block_number) {
    // bfs를 이용하여 가장 큰 블록그룹 탐색
 
    queue<pair<int, int>> q; // Queue
    vector<pair<int, int>> rainbows; // 무지개 블록 좌표 저장 용도
    vector<pair<int, int>> blocks; // 블록 그룹 좌표 저장 용도
 
    q.push(make_pair(y, x));
    blocks.push_back(make_pair(y, x));
    used[y][x] = true;
 
    while (!q.empty()) {
        int sy = q.front().first;
        int sx = q.front().second;
        q.pop();
 
        // 4방향 탐색
        for (int d = 0; d < 4; ++d) { 
            int ny = sy + dy[d];
            int nx = sx + dx[d];
 
            if (ny < 0 || nx < 0 || ny >= N || nx >= N || used[ny][nx]) continue; // 범위를 벗어났거나 사용한 경우
            else if (board[ny][nx] == block_number || board[ny][nx] == RAINBOW) { // 블록 번호가 같거나 무지개 블록인 경우
                blocks.push_back(make_pair(ny, nx));
                q.push(make_pair(ny, nx));
                used[ny][nx] = true;
                if (board[ny][nx] == RAINBOW) // 무지개 블록은 무지개 블록 리스트에 추가
                    rainbows.push_back(make_pair(ny, nx));
            }
        }
    }
    if (compare_block_groups(blocks, rainbows.size(), y, x)) { 
        // 블록 비교 결과 현재 탐색한 블록이 우세한 경우
        best_blocks = blocks;
        best_rainbows = rainbows.size();
        best_start_y = y;
        best_start_x = x;
    }
    
    // 무지개 블록은 중복해서 사용하므로 무지개 블록 좌표들의 used(사용 여부)를 false로 변경
    for (int i = 0; i < rainbows.size(); i++){
        int sy = rainbows[i].first;
        int sx = rainbows[i].second;
        used[sy][sx] = false;
    }
}
bool find_largest_block_group() {
    // 가장 큰 블록 그룹을 찾는 함수
 
    used = vector<vector<bool> >(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!used[i][j] && board[i][j] > 0) // 사용하지 않았거나, 일반 블록인 경우(>0)
                bfs(i, j, board[i][j]);
        }
    }
    // 가장 큰 블록 그룹의 크기가 1보다 큰 경우 True, 같거나 작은 경우 False
    // 알고리즘 종료 조건 : 가장 큰 블록 그룹 크기가 2보다 작은 경우
    return best_blocks.size() > 1; 
}
void delete_best_block_group() {
    // 가장 큰 블록 그룹 삭제 및 점수 획득
    for (int i = 0; i < best_blocks.size(); ++i) {
        int y = best_blocks[i].first;
        int x = best_blocks[i].second;
        board[y][x] = EMPTY;
    }
    score += best_blocks.size() * best_blocks.size();
    
    // 블록 그룹을 사용했으므로, 가장 큰 블록 그룹 정보 초기화
    best_blocks.clear();
    best_rainbows = best_start_y = best_start_x = 0;
}
void work_gravity() {
    // 중력 작용
    for (int i = N - 2; i >= 0; --i) { // N-2부터 0까지 탐색(마지막 행으로부터 첫번째의 행부터 줄여가며)
        for (int j = 0; j < N; ++j) {
            if (board[i][j] == EMPTY || board[i][j] == BLACK) continue; // 비어있거나 검정 블록인 경우 continue
 
            // 현재행(i)의 다음행 부터 탐색하여 EMPTY가 아닐때 가지 행간 블록데이터 교환
            for (int k = i + 1; k < N; ++k) {
                if (board[k][j] == EMPTY) { // (k, j)가 빈 좌표인 경우
                    board[k][j] = board[k-1][j]; // (k, j)에 (k-1, j)의 값 전달
                    board[k-1][j] = EMPTY; // (k-1, j)는 EMPTY로 변경
                }
                else // (k, j)가 빈 좌표가 아닌 경우
                    break;
            }
        }
    }
}
void rotate90() {
    // 배열을 90도회전 시킴
    vector<vector<int >> new_board = vector<vector<int>>(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            new_board[i][j] = board[j][N - i - 1];
        }
    }
    board = new_board;
}
 
int main() {
    // 입력
    cin >> N >> M;
    board = vector<vector<int> >(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> board[i][j];
    // 풀이
    while (find_largest_block_group()){ // 가장 큰 블록이 존재하는 동안 반복
        delete_best_block_group(); // 가장 큰 블록 제거 및 점수 획득
        work_gravity(); // 중력 작용
        rotate90(); // 90도 회전
        work_gravity(); // 중력 작용
    }
 
    cout << score << endl;
}

 

 

감사합니다.