[삼성 기출] 백준 21609번 상어 중학교 풀이

| |
백준 온라인 저지 21609번 - 상어 중학교 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.

블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

  1. 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
  2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
  3. 격자에 중력이 작용한다.
  4. 격자가 90도 반시계 방향으로 회전한다.
  5. 다시 격자에 중력이 작용한다.

격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

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


입력

첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.

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


출력

첫째 줄에 획득한 점수의 합을 출력한다.


제한

  • 1 ≤ N ≤ 20
  • 1 ≤ M ≤ 5


풀이

본 문제와 세트 문제인 상어 초등학교와 아주 유사한 문제이다. 동일하게 구현과 시뮬레이션에 기반한 문제이지만, 그래프 탐색이 가미되었고 격자 내에서의 추가적인 구현 및 조건이 붙었다. 문제의 핵심은 매 턴마다 알맞은 블록 그룹을 찾아내는 것이다. 우선 문제에서 제시한 조건이 상당히 많으므로 문제를 주의깊게 읽어야한다. 요약하자면 검은색 블록은 벽이나 마찬가지이고, 무지개 블록은 그 어느 색이던 될 수 있다. 이것이 조건의 핵심이고, 기준 블록은 그룹 내의 블록 중에서 가장 상단, 그리고 좌측에 있는 블록이다.

모든 블록 그룹들을 탐색하려면 모든 좌표에서 DFS 또는 BFS를 수행해야 할 것이다. 그런데 이 때 주의해야 할 점이 있다. 보통 모든 좌표에서 그래프 탐색을 할 경우, visited와 같은 방문 기록을 저장하는 배열을 두고 이미 한 번이라도 방문했던 좌표에서는 효율성을 위해 아예 탐색을 하지 않는 경우가 많은데 이 문제에서는 이 방식으로 하면 틀린다. 바로 무지개 블록 때문이다. 무지개 블록은 여러 블록 그룹들끼리 공유될 수 있기 때문에, 매 좌표마다 그래프 탐색이 끝나면 visited 배열을 초기화하여 무지개 블록이 다른 블록 그룹 탐색에서도 방문될 수 있게끔 해야한다.

매 턴마다 알맞은 블록 그룹을 골라내는 작업은 구조체와 정렬을 이용하면 간단하다. 이러한 블록 그룹들을 저장하는 구조체를 선언하고, 문제의 조건에 맞게 비교 연산자를 오버라이딩 한다. 그러면 매 턴마다 모든 블록 그룹 후보들을 벡터에 넣고 정렬하면 벡터의 맨 앞에서 가장 알맞은 블록 그룹을 찾을 수 있다.

그리고 문제를 푸는 과정에서 블록 그룹을 삭제할 때 격자에서 빈 칸을 정의할 일이 생긴다. 이는 문제에서 사용되지 않은 -2 와 같은 음수로 표현해주면 코드 작성 과정에서 검은색 블록과 빈 칸을 쉽게 묶을 수 있어 효율적이다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int EMPTY = -2;

int N,M;
int board[20][20];
bool visited[20][20];
int dy[] = {-1,1,0,0};
int dx[] = {0,0,-1,1};

int cnt, rainbow, by=1e9, bx=1e9;

struct Point {
    int y,x;
    Point(int y, int x):y(y),x(x){}
};

vector<Point> points;

struct Group {
    int size; // 블록 그룹 크기
    int rainbow; // 무지개 블록 갯수
    int by,bx; // 기준 블록 좌표
    vector<Point> points; //포함 블록 좌표
    Group(int size, int rainbow, int by, int bx, vector<Point> points)
        :size(size),rainbow(rainbow),by(by),bx(bx),points(points){}

    // 정렬을 위한 비교 연산자 오버라이딩
    bool operator < (const Group& g) {
        if(size == g.size) {
            if(rainbow == g.rainbow) {
                if(by == g.by) return bx > g.bx;
                return by > g.by;
            }
            return rainbow > g.rainbow;
        }
        return size > g.size;
    }
};

bool inRange(int y, int x) {
    return 0<=x && x<N && 0<=y && y<N;
}

// 블록 그룹 찾기
void dfs(int y, int x, int num) {
    visited[y][x] = true;
    points.push_back(Point(y,x));

    // 기준 블록 갱신
    if(board[y][x] != 0) {
        if(y < by) {
            by = y;
            bx = x;
        }
        else if(y == by) bx = min(bx,x);
    }
    else rainbow++;

    for(int i=0;i<4;i++) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(!inRange(ny,nx) || visited[ny][nx] || board[ny][nx]!=0 && board[ny][nx]!=num)
            continue;
        dfs(ny,nx,num);
    }

    cnt++;
}

// 중력 적용
void gravity() {
    for(int i=N-1;i>=0;i--) {
        for(int j=0;j<N;j++) {
            if(board[i][j] < 0) continue;

            int y=i, x=j;
            while(inRange(y+1,x) && board[y+1][x]==EMPTY) {
                board[y+1][x] = board[y][x];
                board[y][x] = EMPTY;
                y++;
            }
        }
    }
}

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

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

    cin>>N>>M;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>board[i][j];
    
    int ans = 0;
    while(1) { 
        vector<Group> v;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(board[i][j] <= 0) continue;

                memset(visited,0,sizeof(visited)); // 방문 기록 초기화

                dfs(i,j,board[i][j]);

                if(cnt > 1) v.push_back(Group(cnt,rainbow,by,bx,points));

                cnt = rainbow = 0;
                by = bx = 1e9;
                points.clear();
            }
        }

        sort(v.begin(),v.end());

        // 더 이상 블록 그룹이 없을 경우 종료
        if(v.size() == 0 || v[0].size < 2) {
            cout<<ans;
            return 0;
        }

        for(Point& p:v[0].points)
            board[p.y][p.x] = EMPTY;

        ans += v[0].size * v[0].size;

        gravity();
        rotate();
        gravity();
    }
    
    return 0;
}
0%