[BOJ] 백준 21609 상어 중학교

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

Approach

2021 상반기 2번 문제로 BFS 유형 문제이다.

▶ BFS (Breadth-First Search, 너비 우선 탐색)  

BFS (Breadth-First Search, 너비 우선 탐색)

 

문제에서 요구하는 아래 사항을 구현하면 된다.

① 크기가 가장 큰 블록 그룹을 찾는다. 

    그러한 블록 그룹이 여러개이면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,

    그러한 블록도 여러개이면 기준 블록의 행이 가장 큰 것을, 

    그것도 여러개이면 열이 가장 큰 것을 찾는다.

우선순위 3, 4 번째 조건에서 행과 열이 보다 큰 항목이 있는데

for문으로 이중탐색할 때, (0, 0) ~ (N, N) 순으로 하면서 충족할 수 있다.

 

같은 색상(무지개색 포함)이면서 인접한 영역인 블록 그룹을 BFS()로 찾는다.

무지개색은 여러 색과 그룹을 형성할 수 있으므로 colorUsed[][]에 표시하지 않지만

일반(?) 색은 colorUsed[][]에 표시해서 블록 그룹의 기준 블록을 선정할 수 있다.

(블록 그룹의 기준 블록은 행/열이 작은 것으로, BFS의 출발지점에 해당한다.)

 

② 찾은 블록 그룹의 모든 블록을 제거한다.

    블록 그룹에 포함된 블록의 수를 B라고 했을 때, B × B 점을 획득한다.

- BFS() 할 때, 그룹을 형성한 블록들을 vector에 저장

- BFS() 시작할 때마다 vector를 clear 해주어야 한다.

 

③ 격자에 중력이 작용한다.

- 중력은 열(j) 기준으로 작용한다.

- 블록이 내려올 때, 멈추는 지점(bottom)을 설정한다.

    ex) bottom은 경계선 위 / 다른 블록 위

- 검은색 블록은 중력으로는 움직이지 않는다. 

 

④ 격자가 90도 반시계 방향으로 회전한다.

▶ 행렬 90° 회전 (문제 풀 때, 자주 사용되는 skill)

행렬 90° 회전 (C 언어)

⑤ 다시 격자에 중력이 작용한다.

- 함수로 중력을 구현해서 재활용한다.

---

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

enum {
    RAINBOW = 0,
    BLACK = -1,
    NONE = -2,
};

const int MAX_N = 20 + 2;
const int dx[4] = { -1, 1,  0, 0 };
const int dy[4] = {  0,  0,-1, 1 };

struct Node
{
    int x, y;
};

struct Group
{
    int size, rainbowCnt;
};

int N, M, ans, cnt;
int map[MAX_N][MAX_N], tmp[MAX_N][MAX_N];
bool ret, visited[MAX_N][MAX_N], colorUsed[MAX_N][MAX_N];
vector<Node> blockList, targetList;

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
}

Group BFS(int r, int c) {
    // 임시 블록 그룹
    Group group = { 1, 0 };
    // 큐 초기화
    queue<Node> que;
    que.push({ r,c });
    // 방문 표시 초기화
    memset(visited, 0, sizeof(visited));
    visited[r][c] = colorUsed[r][c] = true;
    // 블록 목록 초기화
    blockList.clear();
    blockList.push_back({ r, c });

    while (!que.empty()) {
        Node cur = que.front(); que.pop();
        for (int k = 0; k < 4; k++) {
            int nextX = cur.x + dx[k];
            int nextY = cur.y + dy[k];
            // 범위를 벗어난 경우
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)
                continue;

            // 이미 방문한 경우
            if (visited[nextX][nextY])
                continue;

            // 같은 색상이거나 무지개색인 경우
            if (map[nextX][nextY] == map[r][c] || map[nextX][nextY] == RAINBOW) {
                // 블록 그룹의 블록 개수 증가
                group.size++;
                // 무지개색 블록인 경우
                if (map[nextX][nextY] == RAINBOW)
                    group.rainbowCnt++;
                // 무지개색이 아닌 일반 색깔인 경우
                else
                    colorUsed[nextX][nextY] = true;
                
                que.push({ nextX,nextY });
                // 중복 방문하지 않기 위한 처리
                visited[nextX][nextY] = true;
                // 나중에 제거해야할 블록 그룹일 수 있으므로 담아둔다.
                blockList.push_back({ nextX, nextY });
            }
        }
    }
    return group;
}

bool getBlockGroup() {
    ret = false;
    Group pivot = { 0, 0 };
    memset(colorUsed, 0, sizeof(colorUsed));
    
    for (int r = 0; r < N; r++) 
    {
        for (int c = 0; c < N; c++) 
        {
            // 삭제되거나 이동되어 비어 있는 경우 + 검은색 블록인 경우
            if (map[r][c] == NONE || map[r][c] == BLACK)
                continue;

            // 기준 블록이 될 수 없는 무지개색이거나 이미 방문한 블록인 경우
            if (map[r][c] == RAINBOW || colorUsed[r][c])
                continue;
            
            // 기준 블록 탐색
            Group blockGroup = BFS(r, c);

            // 해당 그룹 크기가 조건을 만족하지 못한다면
            if (blockGroup.size < 2) continue;

            if (pivot.size <= blockGroup.size) 
            {
                // 해당 그룹이 가진 블록 개수가 동일한 경우, 무지개 블록 개수 비교
                if (pivot.size == blockGroup.size 
                    && pivot.rainbowCnt > blockGroup.rainbowCnt)
                    continue;

                // 새로운 기준 선정
                pivot = { blockGroup.size, blockGroup.rainbowCnt };
                // 제거해야될 블록 목록 (후보)
                targetList = blockList;
                ret = true;
            }
        }
    }

    // 블록 그룹을 찾지 못한 경우
    if (!ret)
        return false;

    // 블록 그룹을 찾은 경우
    cnt = 0;
    for (Node tg : targetList)
    {
        cnt++;
        map[tg.x][tg.y] = NONE; // 블록 삭제
    }
    ans += (cnt * cnt);
    return ret;
}

void gravity() {
    // 모든 열에 대해서
    for (int j = 0; j < N; j++) {
        int bottom = N - 1;
        // 제일 아래행부터 위로
        for (int i = N - 1; i >= 0; i--) {
            // 블록이 삭제되었거나 이동된 칸인 경우
            if (map[i][j] == NONE)
                continue;
            // 검은색 블록인 경우, (가상의) 바닥으로 설정
            else if (map[i][j] == BLACK)
                bottom = i - 1; // 바닥에서 한칸 위 (블록이 내러와서 멈추는 지점)
            else
            {
                int block = map[i][j];
                map[i][j] = NONE;
                map[bottom--][j] = block;
            }
        }
    }
}

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

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = tmp[i][j];
        }
    }
}

int main() {
    input();
    while (getBlockGroup()) {
        gravity();
        rotate();
        gravity();
    }
    printf("%d\n", ans);
}