boj, 백준) 21609. 상어중학교 (C/C++)

1. 문제 링크

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

21609번: 상어 중학교

2. 문제 개요

N x N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. 인접한 칸은 상 하 좌 우에 있는 칸으로 정의한다.

 

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

 

블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 불록, 그러한 블록이 여러 개면 열의 번호가 가장 작은 블록이다.

 

규칙이 다음과 같을 때, 얻을 수 있는 점수를 구하는 프로그램을 작성하시오.

 

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

 

3. 문제 힌트

문제를 잘 읽는 것이 힌트.

 

크기가 가장 큰 블록 그룹을 찾자 -> BFS로 구현할 수 있다. 같은 숫자끼리 묶어주도록하자.

BFS 할 때, 방문했음을 나타내는 배열을 체크할 텐데, 무지개 블록은 여러 블록에 포함될 수 있다. 이럴 때, BFS를 어떻게 진행해야 할까..?

 

 

블록의 기준을 정해야 한다. 블록 그룹의 가장 위쪽의 가장 왼쪽이다.

조건에 맞는 블록들이 여러 개 있을 때, 우선시되는 블록 그룹은 위에 정의한 기준 블록이 가장 밑의 가장 오른쪽에 있는 것이다.

 

중력이 작용하는 것은 맵을 전체적으로 밑으로 내리는 것. -> 검은색 블록은 내려가지 않기 때문에, 한 칸씩 한칸씩 밑을 탐색해보고 다른 블록이 있는지, 검은색 블록이 있는지 체크해야 한다. 나중에 또 내려야 하기 때문에 함수 형태로 구현하자.

 

반시계로 회전하는 부분은 규칙이 존재하기 때문에 직접 그려보며 하는 것이 좋다.

 

4. 문제 풀이

이번 문제는 큰 아이디어?라고 하기보다는 문제에 주어진대로 잘 구현하면 되는 문제다.

 

우선, BFS로 탐색을 먼저 했다.

맵은 모두 훑으면서 빈칸, 검은색 블록, 무지개 블록, 이미 방문했던 블록이 아닌 곳을 기준으로 BFS를 시작했다.

 

BFS를 하면서, 방문했음을 나타내야 할 텐데, 무지개 블록은 탐색이 끝나면 방문을 지워줘서 다른 블록을 기준으로 하는 BFS에서 또 방문할 수 있도록 해주었다.

특별한 점은 조건을 만족시켜주기 위해 각 블록 그룹을 1개 만들 때, 기준이 되는 위치, 블록 그룹 내의 무지개 블록 개수 등을 기억했다.

 

맵을 내릴 때는 가장 밑에서부터 밑을 훑어가며 빈칸이 존재하는지 체크하면서 내려갈 곳을 체크했다.

 

반시계 방향으로 회전할 때, 그냥 배열의 크기가 많지 않아서 여분의 배열을 만들고 복사해주도록 했다. (간단히)

 

이번 문제는 특별한 알고리즘(?)이랄까.. 그냥 문제의 내용대로 구현을 하면 되기 때문에, 간단한 흐름(?)만 잘 캐치한다면 쉬울 거라고 생각합니다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;

struct COORD {
	COORD(){}
	COORD(int y_, int x_):y(y_),x(x_){}
	int y, x;
};

int n, m, ans;
constexpr int NOBLOCK = -2;
int map[20][20];
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };

void RotateMap()
{
	int rotatedMap[20][20];
	
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < n; ++j)
			rotatedMap[n-1-j][i] = map[i][j];
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			map[i][j] = rotatedMap[i][j];

	return;
}

void MoveDown()
{
	for (int j = 0; j < n; ++j) {
		for (int i = n - 1; i >= 0; --i) {
			if (map[i][j] != -1 && map[i][j] != NOBLOCK) {
				
				int ptr = i;
				int cur = map[i][j];
				map[i][j] = NOBLOCK;

				while (ptr + 1 < n && map[ptr + 1][j]== NOBLOCK) 
					++ptr;
				
				map[ptr][j] = cur;
			}
		}
	}
	return;
}

int main()
{
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) 
			scanf("%d", &map[i][j]);
		

	while (1) {

		int blockSize = 0;
		int rainbowNum = 0;
		COORD block;
		int curColor = NOBLOCK;
		vector<COORD> rainbow;
		bool visited[20][20] = { false, };
		bool endFlag = true;

		//BFS
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (visited[i][j] == false && !(map[i][j] == -1 || map[i][j] == 0 || map[i][j] == NOBLOCK))
				{
					int curBlockSize = 0;
					queue<COORD> q;
					q.push(COORD(i, j));
					visited[i][j] = true;
					curColor = map[i][j];

					while (!q.empty())
					{
						COORD cur = q.front(); q.pop();
						++curBlockSize;
						for (int dir = 0; dir < 4; ++dir) {
							COORD next;
							next.y = cur.y + dy[dir];
							next.x = cur.x + dx[dir];

							if (next.y < 0 || next.x < 0 || next.x >= n || next.y >= n || map[next.y][next.x] == -1 ||visited[next.y][next.x] || map[next.y][next.x] == NOBLOCK)
								continue;

							if (map[next.y][next.x] == 0 || map[next.y][next.x] == curColor) {
								
								visited[next.y][next.x] = true;
								q.push(next);
								
								if (map[next.y][next.x] == 0) {
									rainbow.push_back(next);
								}	
							}
						}
					}
					
					if (curBlockSize >= 2)
						endFlag = false;
						

					if (blockSize < curBlockSize){
						blockSize = curBlockSize;
						rainbowNum = rainbow.size();
						block = COORD(i, j);
					}
					else if (blockSize == curBlockSize) {
						if (rainbowNum < rainbow.size())
						{
							rainbowNum = rainbow.size();
							block = COORD(i, j);
						}
						else if (rainbowNum == rainbow.size())
						{
							if (block.y < i)
								block = COORD(i, j);
							else if (block.y == i)
								if (block.x < j)
									block = COORD(i, j);
							
						}
					}

					for (COORD item : rainbow) 
						visited[item.y][item.x] = false;

					rainbow.clear();
				}
			}
		}

		if (endFlag)
			break;
		ans += blockSize * blockSize;
		memset(visited, false, sizeof(visited));

		queue<COORD> q;
		q.push(block);
		visited[block.y][block.x] = true;
		curColor = map[block.y][block.x];

		while (!q.empty()) {
			COORD cur = q.front(); q.pop();
			map[cur.y][cur.x] = NOBLOCK;

			for (int dir = 0; dir < 4; ++dir) {
				COORD next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];

				if (next.y < 0 || next.x < 0 || next.x >= n || next.y >= n || map[next.y][next.x] == -1 || visited[next.y][next.x] || map[next.y][next.x] == NOBLOCK)
					continue;

				if (map[next.y][next.x] == 0 || map[next.y][next.x] == curColor) {

					visited[next.y][next.x] = true;
					q.push(next);
				}
			}
		}


		MoveDown();
		RotateMap();
		MoveDown();
	}
	
	printf("%d\n", ans);
	
	return 0;
}

 

 

6. 결과