[BOJ] 11559 Puyo Puyo

Link https://www.acmicpc.net/problem/11559

Note

조건이 몇개 걸려있어서 약간 까다로웠던 문제
얼마나 연결될지 몰라서 일단은 BFS로 풀었다. 기존 문제들과 다른 점이라면 최소 4개가 연결 되어 있어야 하기 때문에
무턱대고 방문 했다고 값을 . 으로 바꿔주면 안됬다.
일단은 연결 되어있는 개체 수를 저장하고 나중에 그 값이 4가 넘어가는 라벨에 한해서만 터진 경우로 바꿔 주어야 한다.
또한 지워진 경우 위의 값을 당겨야 하기 때문에 정리를 해주는 부분이 따로 필요했다.

입력값이 역순으로 들어오기 때문에 배열에도 역순으로 저장해 주는게 생각하면서 풀기 편했다.

알고리즘

1. 현재 상태를 입력 받는다.
2. 현재 상태에서 지워질 수 있는 경우가 있는지 확인하고 존재 한다면 터진 위치를 . 으로 바꿔준다.
   1. 방문 확인과 Labeling을 수행할 맵과 같은 크기의 배열을 생성한다.
   2. BFS를 통해 Labeling을 수행하면서 해당 라벨에 연결 개체 수를 저장한다.
   3. 각 라벨에 대해서 개체의 수가 4 이상인 경우 해당 부분을 . 으로 바꾼다.
   4. 터진 경우가 존재한다면 true를 반환 한다.
3. 터진 상태에 중력을 적용한 것을 계산한 후 현재 상태로 갱신한다.
   1. 각각의 위치에 대해서 빈 곳을 계산하고 다음 뿌요가 있는 곳을 탐색한다.
   2. 현재 공백 위치와 다음 뿌요와의 거리의 합이 맵 밖으로 판정되면 다음 라인을 탐색한다.
   2. 합이 맵 안이라면 해당 뿌요를 공백의 위치로 바꿔주고 다음 공백 노드로 이동한다.
4. 2 - 3 의 결과를 출력한다.

소스코드

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

using namespace std;

const int ROW = 12;
const int COL = 6;
const int MAX_LABEL = 72;

char board[ROW][COL+1];
const short posX[4] = { 1, 0, -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };

struct Point {
	short x;
	short y;

	Point() {}
	Point(short x, short y) : x(x), y(y) {}
};

bool removePuyo()
{
	bool res = false;
	queue<Point> q;
	vector<int> connectCount(MAX_LABEL);

	// 제거
	int label = 1;
	short visitTable[ROW][COL] = {};

	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			if (visitTable[i][j] != 0 || board[i][j] == '.')
				continue;

			q.push(Point(i, j));

			while (!q.empty())
			{
				Point cur = q.front();
				q.pop();

				if (visitTable[cur.x][cur.y])
					continue;

				visitTable[cur.x][cur.y] = label;
				connectCount[label -1]++;

				for (int pos = 0; pos < 4; pos++)
				{
					short nextX = cur.x + posX[pos];
					short nextY = cur.y + posY[pos];

					if (0 <= nextX && nextX < ROW && 0 <= nextY && nextY < COL)
						if (board[nextX][nextY] != '.' && board[nextX][nextY] == board[cur.x][cur.y])
							q.push(Point(nextX, nextY));
				}
			}

			label++;
		}
	}

	for (int i = 0; i < MAX_LABEL; i++)
	{
		// 값이 4가 넘는 경우에만 터진 것으로 판정
		if (connectCount[i] < 4)
			continue;

		// 터진 경우가 존재한다.
		if (res == false)
			res = true;

		for (int j = 0; j < ROW; j++)
			for (int k = 0; k < COL; k++)
				if (visitTable[j][k] == i+1)
					board[j][k] = '.';
	}

	return res;
}

void refreshBoard()
{
	for (int i = 0; i < COL; i++)
	{
		int target = 1, base = 0; // 목표지점, 현재 지점

		while (base + target < ROW)
		{
			if (board[base][i] != '.') // 공백 지점 탐색
				base++;
			else if (board[target + base][i] == '.') // 바꿔야할 지점 탐색
				target++;
			else // 현재 지점이 공백 이면서 바꿔야 할 지점이 Puyo인 경우
			{
				swap(board[base][i], board[base + target][i]);
				base++;
				target = 1;
			}
		}
	}
}

int solution()
{
	int count = 0;
	// 제거 및 확인 // 제거되면 +1
	for (; removePuyo(); count++)
		refreshBoard(); // 빈칸 채우기
	
	return count;
}

int main()
{
	for (int i = ROW - 1; i >= 0 ; --i)
		cin >> board[i];

	cout << solution();

	return 0;
}

2019-01-13 11:30:00에 Tistory에서 작성되었습니다.