Baekjoon11559-Puyo Puyo

백준 사이트 11559 - Puyo Puyo 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

BFS문제입니다.
백준에서는 Gold5의 난이도를 책정하고 있습니다.
?

---

4. 생각한 것들

• 피곤한 상태에서 작성한 코드라 매우 더럽습니다. 의식의 흐름대로 코드를 짰습니다. 로직 자체는 그래도 다른 사람들보다 이해하기 쉽게 짜긴 했습니다.. Down부분이 이해하기 힘들 뿐
• 일반 문제와 다르게 중력이라는 특이한 상황이 작용합니다. 사실 이러한 문자옮기기는 예전 카카오 코테때도 나왔던 것입니다.. 잘해둡시다.
• 신경 써줘야할 것은 ‘중력’이라는 점과 ‘방문 처리’의 적절한 시기입니다.
• 푸요를 한번에 다 터트려야한다는 말을 잘 생각해봐야합니다.
• 또한 변수들의 값을 중력으로 인해 내려줄 때 인덱스 범위도 잘 고려해서 코드를 짜야합니다. 18%에서 틀리는건 인덱스범위에서 문제가 나는 것입니다.
• 100%에서 틀리는건 푸요가 하나도 안들어왔을 때 오류가 뜬다고 하더군요.
• 다행히도 시간제한이 1초지만 그냥 막탐색해도 시간초과는 안뜨는 것 같습니다. 범위가 작아서 그런가봅니다.
• 푸요가 박살나는 과정을 보고 싶으면 주석문을 풀어서 보시길 바랍니다.

---

5. code

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


char MAP[13][7] = { '0' };
bool v[13][6] = { false, };
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };


void Input() {
	for (int i = 0; i < 12; ++i)
	{
		for (int j = 0; j < 6; ++j)
			cin >> MAP[i][j];
	}
}

bool BFS(int i, int j, char remove)
{
	queue<pair<int, int>> q;
	queue<pair<int, int>> countPuyo;
	q.push(make_pair(i, j));
	countPuyo.push(make_pair(i, j));
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; ++k)
		{
			int newX = x + dx[k];
			int newY = y + dy[k];
			if (0 <= newX && newX < 12 && 0 <= newY && newY < 6 && MAP[newX][newY] == remove && v[newX][newY] == false)
			{
				countPuyo.push(make_pair(newX, newY));
				v[newX][newY] = true;
				q.push(make_pair(newX, newY));
			}
		}

	}
	if (countPuyo.size() >= 4)
	{
		while (!countPuyo.empty())
		{
			int x = countPuyo.front().first;
			int y = countPuyo.front().second;
			countPuyo.pop();
			MAP[x][y] = '.';
		}
		return true;
	}
	return false;
}

void swap(int start, int end, int col)
{
	int range = start - end;
	//cout << "start " << start << " end " << end << " col" << col << '\n';
	for (int i = 0; i < lange; ++i)
	{
		char temp = MAP[start][col];
		MAP[start][col] = MAP[end][col];
		MAP[end][col] = temp;
		--start;
		--end;
		if (end < 0)
			break;
	}
}

void Down() {

	bool check = false;

	for (int i = 0; i < 6; ++i)
	{
		int start = 13;
		for (int j = 11; j >= 0; --j)
		{
			if (MAP[j][i] == '.' && !check)
			{
				start = j;
				check = true;
			}
			if (MAP[j][i] != '.' && start != 13)//어디선가  걸리긴했고 문자를 만낫을 때
			{
				int end = j;// 걸린곳의 높이
				//cout << "start" << start << "end" << end <<"i"<<i<< '\n';
				swap(start, end, i);
				check = false;
				j = 11;
				start = 13;
				continue;

			}
		}
		check = false;
	}
}
void printMAP()
{
	for (int i = 0; i < 12; ++i)
	{
		for (int j = 0; j < 6; ++j)
			cout << MAP[i][j] << " ";
		cout << '\n';
	}
	cout << '\n';
}
void Solve() {

	int result = 0;
	bool check = false;
	bool counting = true;
	while (counting)
	{
		check = false;
		counting = false;
		memset(v, false, sizeof(v));
		for (int i = 0; i < 12; ++i) {

			for (int j = 0; j < 6; ++j) {
				if (MAP[i][j] != '.' && v[i][j] == false)
				{
					v[i][j] = true;
					check = BFS(i, j, MAP[i][j]);
					if (check == true)
						counting = true;
				}
			}
		}
		if (counting)
			++result;
		//땡겨줌
		//printMAP();
		Down();
		//cout << "땡긴 후\n";
		//printMAP();
	}
	cout << result;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	Solve();

	return 0;
}

---

6. 후기

자면서 풀었다.. 4시간 자고 일어나서 푼 문제..