[삼성기출] 백준 - C++ 상어 중학교

BFS와 구현문제이다.

 

---

1. Solution 코드

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

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

struct Point {
	int x, y;
};

struct Group {
	int size;
	int rainbowCnt;
};

const int MAX_N = 20;
const int MAX_M = 5;
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };

int N, M, ans, cnt;
int map[MAX_N][MAX_N];
vector<Point> blockList, targetList;
bool visit[MAX_N][MAX_N], colorUsed[MAX_N][MAX_N];

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

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() {
	int temp[MAX_N][MAX_N];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			temp[N - 1 - i][i] = map[i][j];
		}
	}

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

Group findGroup(int r, int c) {
	Group g;
	queue<Point> q;
	Point standard = { r, c };
	g.size++;

	memset(visit, 0, sizeof(visit));
	visit[r][c] = colorUsed[r][c] = true;
	blockList.clear();
	blockList.push_back({ r, c });

	q.push(standard);

	while (!q.empty()) {
		for (int dir = 0; dir < 4; dir++) {
			int nextX = q.front().x + dx[dir];
			int nextY = q.front().y + dy[dir];
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N)
				continue;

			if (map[nextX][nextY] == BLACK)
				continue;

			if (visit[nextX][nextY])
				continue;

			if (map[nextX][nextY] == RAINBOW || map[nextX][nextY] == map[standard.x][standard.y]) {
				g.size++;

				if (map[nextX][nextY] == RAINBOW)
					g.rainbowCnt++;
				else
					colorUsed[nextX][nextY] = true;
				
				q.push({ nextX, nextY });
				visit[nextX][nextY] = true;

				blockList.push_back({ nextX, nextY });
			}

		}
	}

	return g;
}

bool getBlockGroup() {
	bool 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] == BLACK || map[r][c] == NONE)
				continue;

			if (colorUsed[r][c] || map[r][c] == RAINBOW)
				continue;

			Group blockGroup = findGroup(r, c);

			if (blockGroup.size < 2)
				continue;

			if (blockGroup.size >= pivot.size) {
				if (blockGroup.size == pivot.size && blockGroup.rainbowCnt < pivot.rainbowCnt)
					continue;

				pivot = { blockGroup.size, blockGroup.rainbowCnt };
				targetList = blockList;
				ret = true;
			}
		}
	}

	if (!ret)
		return false;

	cnt = 0;
	for (Point tg : targetList) {
		cnt++;
		map[tg.x][tg.y] = NONE;
	}
	ans += (cnt * cnt);
	return ret;
}

int main() {
	input();
	while (getBlockGroup()) {
		gravity();
		rotate();
		gravity();
	}

}