백준 21609 상어 중학교
https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
- 빡구현 + BFS이다. 시간 복잡도는 BFS N^2 + 중력 작용 N^2 + rotate N^2 + 중력 작용 N^2 = O(N^2)이다.
1. 가장 큰 블록 그룹 찾기
=> BFS를 통해 블록 그룹을 찾아준다. 이 때,
(1) 범위를 벗어나거나
(2) 해당 칸이 -1이거나
(3) 현재 블록 그룹 번호와 다른 경우는 탐색을 중단한다.
이 과정에서 num_group을 인덱스로 활용하여 블록 그룹을 찾을 때 마다 +1을 해 주고, , block_group[num_group]에 해당 그룹의 좌표를 모두 넣어준다.(temp_xy 벡터)
이 후, block의 size가 2 미만인 경우 탐색을 종료하는데, 이 과정 전에 무지개 블록의 좌표만을 담아서 visited 좌표를 false로 초기화 해 준다. 왜냐하면, 초기화를 하지 않는 경우 다음 블록 그룹을 찾는 과정에서 무지개 블록을 방문하지 않는 문제가 생기기 때문이다.(이 과정에서 많은 시간을 보냈다..)
이 후, 기준 그룹을 구하기 위해 무지개 블록을 제외한 좌표만을 담은 non_rainbow 벡터를 활용하고, compare 함수를 활용하여 기준 블록을 구해준다.
이제 모든 블록 그룹을 구했다면, 이들 중 가장 큰 블록그룹을 찾아준다. 문제에 주어진 조건대로 먼저 크기를 비교하고, 다음으로 무지개 블록 갯수를 비교하고(rainbow_num 배열) 마지막으로 기준 블록을 비교해 준다.
2. 중력 작용
=> 이 부분은 간단하게 구현할 수 있다. 모든 칸에 대해 조사를 할 것이고, 가장 왼쪽의 가장 아래부터 => 위쪽, 오른쪽으로 올라가며 칸이 도착할 위치를 찾는다. 먼저 칸의 값을 저장하고, 아래로 내려가며 -2인 경우일 때(즉, 빈칸일 때) + 맨 아랫칸에 도달할 때 while문을 종료한다. 이 후 해당 위치에 값을 넣어준다. 이 과정을 모든 열에 대해 진행한다.
3. 반시계방향 회전
=> 이 부분은 이 문제를 쉽게 활용한 버전이라고 보면 된다. 여기서는 시계 방향이 아닌, 반시계 방향으로 구현을 해 주면 된다. 따라서 벡터에 넣는 순서만 다르게 해 주면, 쉽게 해결이 된다.
- 구현 난이도 자체는 어렵지 않았지만, 시간이 조금 오래걸리는 문제였다. 신경을 써야 할 부분은 무지개 블록을 탐색 할 때 마다 visited값을 false로 다시 초기화를 해야 한다는 부분이다.
- 모든 테스트케이스를 통과했음에도 계속 틀렸습니다가 떠서 문제를 찾아보니 i와 j를 또 잘못 작성했었다.. 나중에 디버깅할때 참고해야겠다 ㅠ
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int map[20][20];
int n, m;
bool visited[20][20];
int num_group, total_score;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
vector<pair<int, int>> block_group[401];
int rainbow_num[401]; vector<pair<int, int>> base_xy;
void debugging() {
for (int i = 0; i < n; i++) {
for (int j = 0; j <n; j++) {
cout << map[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
}
void rotate() {
for (int i = 0; i < n / 2; i++) {
//모서리 저장
vector<int> line[4];
int now_x = n - 1-i; int now_y = n - 1-i;
for (int j = 0; j < n-(i*2); j++) line[0].push_back(map[now_x - j][now_y]);
now_x = i;
for (int j = 0; j < n - (i * 2); j++) line[1].push_back(map[now_x][now_y - j]);
now_y = i;
for (int j = 0; j < n - (i * 2); j++) line[2].push_back(map[now_x+j][now_y]);
now_x = n-1-i;
for (int j = 0; j < n - (i * 2); j++) line[3].push_back(map[now_x][now_y+j]);
now_x = i; now_y = n - 1 -i;
// 회전하기
for (int j = 0; j < n - (i * 2); j++) map[now_x][now_y-j] = line[0][j];
now_y = i;
for (int j = 0; j < n - (i * 2); j++) map[now_x+j][now_y] = line[1][j];
now_x = n - 1-i;
for (int j = 0; j < n - (i * 2); j++) map[now_x][now_y+j] = line[2][j];
now_y = n - 1-i;
for (int j = 0; j < n - (i * 2); j++) map[now_x-j][now_y] = line[3][j];
}
}
void gravity() {
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (map[j][i] < 0) continue;
int temp_num = map[j][i];
int now_x = j;
while (now_x < n - 1 && map[now_x + 1][i] == -2) now_x++;
map[j][i] = -2; map[now_x][i] = temp_num;
}
}
}
bool compare_base(int x, int y, int nx, int ny) {
if (x == nx) return y > ny;
return x > nx;
}
bool compare(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
void bfs(int x, int y) {
int rainbow = 0;
visited[x][y] = true;
int group_num = map[x][y];
vector<pair<int, int>> temp_xy;
vector<pair<int, int>> rainbow_xy;
queue<pair<int, int>> q;
q.push({ x,y });
temp_xy.push_back({ x,y });
while (!q.empty()) {
int tx = q.front().first;
int ty = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = tx + dx[k]; int ny = ty + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (map[nx][ny] < 0 || (map[nx][ny] > 0 && map[nx][ny] != group_num)) continue;
if (visited[nx][ny]) continue;
if (map[nx][ny] == 0) rainbow_xy.push_back({ nx,ny });
visited[nx][ny] = true;
if (map[nx][ny] == 0) rainbow++;
temp_xy.push_back({ nx,ny });
q.push({ nx,ny });
}
}
for (int i = 0; i < rainbow_xy.size(); i++) {
visited[rainbow_xy[i].first][rainbow_xy[i].second] = false;
}
//일반 블록이 없거나 총 사이즈가 2 미만이면 return
if (temp_xy.size() < 2) return;
for (int i = 0; i < temp_xy.size(); i++) {
block_group[num_group].push_back({ temp_xy[i].first, temp_xy[i].second });
}
rainbow_num[num_group] = rainbow;
// 기준블록 구하기
vector<pair<int, int>> non_rainbow;
for (int i = 0; i < temp_xy.size(); i++) {
if (map[temp_xy[i].first][temp_xy[i].second]) non_rainbow.push_back({ temp_xy[i].first,temp_xy[i].second });
}
sort(non_rainbow.begin(), non_rainbow.end(), compare);
base_xy.push_back(non_rainbow[0]);
num_group++;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
while (1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] > 0 && !visited[i][j])
bfs(i, j);
}
}
if (!num_group) break;
int max_group_index = 0; int max_size = block_group[0].size();
for (int i = 1; i < num_group; i++) {
if (block_group[i].size() < max_size) continue;
else if (block_group[i].size() == max_size) {
if (rainbow_num[max_group_index] > rainbow_num[i]) continue;
else if (rainbow_num[max_group_index] == rainbow_num[i]) {// 무지개 블록 수 마저 같으면
int max_x = base_xy[max_group_index].first; int max_y = base_xy[max_group_index].second;
int new_x = base_xy[i].first; int new_y = base_xy[i].second;
if (compare_base(max_x, max_y, new_x, new_y)) continue;
else {
max_group_index = i;
max_size = block_group[i].size();
}
}
else {
max_group_index = i;
max_size = block_group[i].size();
}
}
else {
max_group_index = i;
max_size = block_group[i].size();
}
}
int removed_block = 0;
for (int i = 0; i < block_group[max_group_index].size(); i++) {
int x = block_group[max_group_index][i].first; int y = block_group[max_group_index][i].second;
map[x][y] = -2; removed_block++;
}
total_score += pow(removed_block, 2);
gravity();
rotate();
gravity();
num_group = 0;
memset(visited, false, sizeof(visited));
memset(rainbow_num, 0, sizeof(rainbow_num));
for (int i = 0; i < n * n; i++) block_group[i].clear();
base_xy.clear();
}
cout << total_score;
return 0;
}