백준 21609 상어 중학교

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

21609번: 상어 중학교

 

- 빡구현 + 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;
}