[C++ 알고리즘] 백준 21609번 : 상어 중학교



Implementation BFS

상어 중학교

풀이과정

상어 초등학교 문제와 마찬가지로 우선순위 큐를 이용해 구현하였다.

1. 크기가 가장 큰 블록 찾기(BFS)     -> find_block()
2. 중력 적용                        -> down()
3. 90도 반시계 방향 회전             -> rotate()
4. 중력 적용                        -> down()

위의 문제 요구사항대로 차근차근 구현만 해주면 쉽게 끝난다.


여기서 헷갈릴만한 부분은 크게 두 가지가 있는 것 같다.

(1) BFS시 무지개 블록 방문 처리

가장 큰 블록을 찾을 때 방문하는 visit 배열에서 무지개 블록을 처리하면 안된다. 나는 새로운 블록 그룹을 만날때마다 bool rainbowVisit[20][20]라는 visit 배열을 새로 만들어주었다.


(2) 우선순위 큐 구현

나는 내 맘대로 info라는 구조체를 만들고 비교함수를 구현했다.

struct info {
	int x, y, cnt = 0, rainbowCnt = 0;
	bool operator<(const info& i) const {
		if (cnt == i.cnt) {
			if (rainbowCnt == i.rainbowCnt) {
				if (x == i.x) return y < i.y;
				else return x < i.x;
			}
			else return rainbowCnt < i.rainbowCnt;
		}
		else return cnt < i.cnt;
	}
};


근데 상어 초등학교 문제도 그렇고 이 문제도 그렇고 tuple<int,int,int,int>을 이용하는 사람이 많더라. tuple은 두 가지의 변수만 저장할 수 있는 pair와 달리 저장할 수 있는 변수에 제한이 없다고 한다. 비교함수도 구현되어있어서 상어중학교같이 비교함수가 간단한 문제의 경우 적극 활용하면 좋을것 같다!

1. 크기가 가장 큰 블록
2. 무지개 개수가 많은 블록
3. 행이 큰 블록
4. 열이 큰 블록

현재 문제 조건에서는 pQ.push({cnt, rainbowCnt, x, y})로 해주면 되고, 여기서 만약 3번 조건이 행이 작은 블록이라면 pQ.push({cnt, rainbowCnt, -x, y}) 이런식으로 작성해서 사용하면 유용할 것 같다.


코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define x first
#define y second
#define BLANK -2

struct info {
	int x, y, cnt = 0, rainbowCnt = 0;
	bool operator<(const info& i) const {
		if (cnt == i.cnt) {
			if (rainbowCnt == i.rainbowCnt) {
				if (x == i.x) return y < i.y;
				else return x < i.x;
			}
			else return rainbowCnt < i.rainbowCnt;
		}
		else return cnt < i.cnt;
	}
};

int res = 0;
int N, M;
int board[20][20];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void input();
bool find_block();	//블록 찾기
void down();		//중력 작용
void rotate();		//반시계 회전

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

	input();
	while (true) {
		int ret = find_block();
		if (!ret) break;			//블록이 없는 경우 종료
		down();
		rotate();
		down();
	}
	cout << res << '\n';

	return 0;
}

void input() {
	//freopen("input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
}

bool find_block() {
	bool visit[20][20] = { false, };
	priority_queue<info> pQ;

	// 블록을 찾아 priority queue에 삽입
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] > 0 && !visit[i][j]) {
				bool rainbowVisit[20][20] = { false, };
				queue<pair<int,int>> Q;
				Q.push({ i,j });
				visit[i][j] = true;

				int cnt = 1, rainbowCnt = 0;
				while (!Q.empty()) {
					int x = Q.front().x;
					int y = Q.front().y;
					Q.pop();

					for (int d = 0; d < 4; d++) {
						int nx = x + dx[d];
						int ny = y + dy[d];

						if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1
							|| visit[nx][ny] || rainbowVisit[nx][ny]) continue;

						if (board[nx][ny] == 0) {
							rainbowVisit[nx][ny] = true;
							Q.push({ nx,ny });
							cnt++;
							rainbowCnt++;
						}
						else if (board[i][j] == board[nx][ny]) {
							visit[nx][ny] = true;
							Q.push({ nx,ny });
							cnt++;
						}
					}
				}

				pQ.push({ i,j,cnt, rainbowCnt });
			}
		}
	}

  // 더 이상 삭제할 블록이 없는 경우 false를 반환하고 main 함수 종료
	if (pQ.empty()) return false;

	// 가장 큰 블록 찾기
	int x = pQ.top().x;
	int y = pQ.top().y;
	int cnt = pQ.top().cnt;

	if (cnt < 2) return false;

	res += cnt * cnt;

	// 블록 삭제 작업 -> 삭제된 블록에는 BLANK(-2) 넣기
	queue<pair<int, int>> Q;
	Q.push({x,y });
	int blockId = board[x][y];
	board[x][y] = BLANK;

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		Q.pop();

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;

			if (board[nx][ny] == 0 ||  board[nx][ny]== blockId) {
				Q.push({ nx,ny });
				board[nx][ny] = BLANK;
			}
		}
	}

	return true;
}

void down() {
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= 0;j--) {
			if (board[j][i] == BLANK) {
				int x = j;
				int y = i;
				while (x > 0 && board[x][y]==BLANK) x--;
				if (board[x][y] == -1) continue;
				board[j][i] = board[x][y];
				board[x][y] = BLANK;
			}
		}
	}
}

void rotate() {
	int tempBoard[20][20];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			tempBoard[i][j] = board[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = tempBoard[j][N-1-i];
		}
	}
}

결과

image