[C++] 백준 11559번: Puyo Puyo

문제 링크

11559번: Puyo Puyo

문제 요약

뿌요뿌요 게임의 현재 상태에서 연쇄가 몇 번 연속으로 일어나는지 알아내야 한다.

접근 방법

1. 매 반복마다 각 열의 맨 아래서부터 '.'가 아닐때까지, 방문하지 않은 뿌요에 대해서 BFS를 돌린다.

• BFS를 돌릴 때, 자신과 인접하고 같은 색의 뿌요인 경우에만 방문을 한다.
• 만약 방문한 뿌요가 4개 이상이면 별도의 벡터에 저장한다.

2. 만약 마지막 열까지 반복을 마쳤는데 벡터가 비어있다면 루프를 탈출한다.
3. 그 외의 경우에는 벡터에 저장된 뿌요를 모두 '.'로 대체한다.
4. 각 열에 대해서 맨 아래부터 순서대로 뿌요 아래에 '.'가 있는 경우에 swap을 해준다.

• 각 열에서 바꿀 것이 없을 때까지 반복을 한다.

5. 위 과정을 진행한 횟수를 출력해준다.

간단한 구현 문제였습니다. $12 \times 6$ 정도의 사이즈라서 어지간히 비효율적인 구현이 아닌이상 쉽게 AC를 받을 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
char puyo[13][7];
bool visited[13][7];
vector<pair<int, int>> v;

void bfs(pair<int, int> start, char c)
{
	queue<pair<int, int>> q;
	q.push(start);
	visited[start.first][start.second] = true;

	vector<pair<int, int>> tmp;
	while (!q.empty())
	{
		pair<int, int> now = q.front();
		q.pop();
		tmp.push_back(now);

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> next = { now.first + dir[i][0], now.second + dir[i][1] };
			if (next.first >= 1 && next.first <= 12 && next.second >= 1 && next.second <= 6
				&& puyo[next.first][next.second] == c && !visited[next.first][next.second])
			{
				q.push(next);
				visited[next.first][next.second] = true;
			}
		}
	}

	if (tmp.size() >= 4)
		for (auto& i : tmp)
			v.push_back(i);
}

int main(void)
{
	for (int i = 1; i <= 12; i++)
		for (int j = 1; j <= 6; j++)
			cin >> puyo[i][j];

	int cnt = 0;
	while (1)
	{
		for (int i = 1; i <= 6; i++)
		{
			for (int j = 12; j >= 1; j--)
			{
				if (puyo[j][i] == '.')
					break;
				if (visited[j][i])
					continue;
				bfs({ j, i }, puyo[j][i]);
			}
		}
		
		if (v.empty())
			break;

		for (auto& i : v)
			puyo[i.first][i.second] = '.';

		for (int i = 1; i <= 6; i++)
		{
			while (1)
			{
				bool check = false;
				for (int j = 12; j >= 2; j--)
				{
					if (puyo[j][i] == '.' && puyo[j - 1][i] != '.')
					{
						swap(puyo[j][i], puyo[j - 1][i]);
						check = true;
					}
				}

				if (!check)
					break;
			}
		}

		memset(visited, false, sizeof(visited));
		v.clear();
		cnt++;
	}

	cout << cnt;
	return 0;
}