[C++] 백준 21609번: 상어 중학교

🔗 문제

21609번: 상어 중학교

21609번: 상어 중학교

 

🖍 풀이

 

6달전에 푼거보다 개선되어서 다시 올리는 풀이 ✌🏻

 

 

문제를 읽고 코드 흐름을 간단하게 정리해보자.

while(flag)
{
	//1. 블럭 그룹들 찾기 
	//2. 조건에 맞는 블럭 제거하고 점수 얻기
	// => 블럭 없으면 종료 flag = false 
	//3. 아래로 중력 작용
	//4. 반 시계 방향으로 회전
	//4. 아래로 중력 작용
}

 

조건 정리

 

✔️ 맵의 상태는 3가지의 블럭 종류와 빈 칸으로 이루어진다.

enum BLOCK
{
    BLACK = -1, 
    RAINBOW = 0, 
    EMPTY = -2
    // 1 ~ M 까지의 숫자는 일반 블럭이다.
};

 

✔️ 블럭 그룹 조건

struct Group
{
	Group() = default;
	int rainbow_cnt = 0;
	pii standard = { MAX, MAX }; // 기준 블럭
	std::vector<pii> blocks;
};

 

사이즈가 같은 블럭 그룹에서 없애야할 블럭을 찾기 위해 정렬을 해주어야 한다.

✔️ 우선순위

1. 총 블럭 크기
2. 무지개 블럭의 개수
3. 기준 블럭의 X
4. 기준 블럭의 Y

struct cmp
{
	bool operator()(const Group& a, const Group& b)
	{
		if (a.blocks.size() == b.blocks.size())
		{
			if (a.rainbow_cnt == b.rainbow_cnt)
			{
				if (a.standard.first == b.standard.first)
					return a.standard.second > b.standard.second;

				return a.standard.first > b.standard.first;
			}
			return a.rainbow_cnt > b.rainbow_cnt;
		}
		return a.blocks.size() > b.blocks.size();
	}
};

나미지는 코드의 소스를 참고하는게 더 도움이 될 것 같아요.

 

💾  소스

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <memory.h>

typedef std::pair<int, int> pii;
typedef std::vector<std::vector<int>> Arr2;

const int MAX = 20 + 1;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };

Arr2 map;
int N, M;
bool visited[MAX][MAX] = { false, };

bool isValid(const int x, const int y)
{
	if (x < 0 || y < 0 || x >= N || y >= N)
		return false;
	return true;
}

void initialize(Arr2& inp)
{
	inp.resize(N, std::vector<int>(N, EMPTY));
}

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


struct Group
{
	Group() = default;
	int rainbow_cnt = 0;
	pii standard = { MAX, MAX };
	std::vector<pii> blocks;
};

struct cmp
{
	bool operator()(const Group& a, const Group& b)
	{
		if (a.blocks.size() == b.blocks.size())
		{
			if (a.rainbow_cnt == b.rainbow_cnt)
			{
				if (a.standard.first == b.standard.first)
				{
					return a.standard.second > b.standard.second;
				}
				return a.standard.first > b.standard.first;
			}
			return a.rainbow_cnt > b.rainbow_cnt;
		}

		return a.blocks.size() > b.blocks.size();
	}
};

Group findGroup(const pii& target)
{
	Group g;
	g.blocks.push_back(target);
	g.standard = target;

	std::queue<pii> q;
	q.push(target);

	visited[target.first][target.second] = true;
	int target_color = map[target.first][target.second];
	std::vector<pii> rainbow_pos;

	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();

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

			if (!isValid(x, y) || visited[x][y] || map[x][y] == BLACK)
				continue;

			if (map[x][y] == RAINBOW)
			{
				++g.rainbow_cnt;
				rainbow_pos.push_back({ x, y });
			}
			else if (map[x][y] == target_color)
			{
				// 그룹에 블럭이 들어올 때마다 기준블럭 갱신
				if (g.standard.first > x)
					g.standard.first = x;
				else if (g.standard.first == x && g.standard.second > y)
					g.standard.second = y;
			}
			else // 그룹에 있는 블럭은 모든 같은 색이어야 하기 때문에 타겟 컬러가 아니면 패스
				continue;

			visited[x][y] = true;
			q.push({ x, y });
			g.blocks.push_back({ x, y });
		}
	}

	for (const auto& p : rainbow_pos)
	{
		// 무지개 블럭은 다른 그룹에도 속할 수 있도록 해야 한다. 
		visited[p.first][p.second] = false;
	}

	return g;
}

Arr2 rotate270(const Arr2& inp)
{
	Arr2 out;
	initialize(out);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			out[N - j - 1][i] = inp[i][j];
		}
	}

	return out;
}

Arr2 gravity(const Arr2& inp)
{
	Arr2 out;
	initialize(out);

	// 세로 한줄씩
	for (int j = 0; j < N; ++j)
	{
		// 아래에서부터
		int h = N - 1;
		for (int i = N - 1; i >= 0; --i)
		{
			//블랙이면 블랙 그대로 두고 이 블럭 위에서부터 시작함
			if (inp[i][j] == BLACK)
			{
				out[i][j] = BLACK;
				h = i - 1;
			}
			//비어있는 곳 있으면 얘 위에 잇는 숫자가 올수잇게 해야함
			else if (inp[i][j] != EMPTY)
				out[h--][j] = inp[i][j];
		}
	}

	return out;
}

int getAnswer()
{
	int answer = 0;

	while (true)
	{
		std::vector<Group> gs;
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (map[i][j] < 1 || visited[i][j]) continue;

				auto g = findGroup({ i, j });
				if (g.blocks.size() > 1)
					gs.push_back(g);
			}
		}

		if (gs.empty())
			return answer;

		std::sort(gs.begin(), gs.end(), cmp());
		answer += (gs[0].blocks.size() * gs[0].blocks.size());
		for (const auto& p : gs[0].blocks)
			map[p.first][p.second] = EMPTY;

		auto step1 = gravity(map);
		auto step2 = rotate270(step1);
		map = gravity(step2);

	}

	return answer;
}

int main()
{
	std::cin >> N >> M;
	initialize(map);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			std::cin >> map[i][j];
		}
	}

	std::cout << getAnswer();

	return 0;
}