[백준/C++] #11559 Puyo Puyo (BFS)

문제

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

 

풀이 (1h 16m / 한번에 O)

뭐 거창한거 없이 그냥 하라는 대로 하면 되었다. 

 

한 시점에 터지는건 하나로 치니까, 시점을 반복문(while)을 통해 구분하자는 생각이 들었다. 그래서 반복문 안에서 flag를 통해 한 시점에 터지는게 있는지를 나타냈다. flag가 0이면 그냥 반복문을 나가고, 연쇄가 몇번 연속으로 일어났는지 출력해줬다. 

 

터지는지 파악하는 데에 bfs를 사용했다. 왜냐하면 동서남북 인접한 곳에 4개의 같은 색의 칸이 있는지 파악을 해야 했기 때문이다. 그렇게 4개 이상의 같은 색의 칸이 인접해있으면, 탐색했던 곳이 기록된 visited 배열을 사용해 해당 위치를 터뜨렸다. 동시에 더 터뜨릴 칸들이 없으면, 중력으로 떨어뜨리게끔 했다. 떨어뜨리는 로직은 정말 그냥 직관적으로 빈칸이 있으면 전부다 한칸씩 내리는 방식으로 구현했다. 더 시간복잡도 작은 로직으로 짜려다 실패했다..ㅋㅋ

 

이렇게 생각보다 직관적인 로직으로 구현했다. 풀이를 한 줄 요약하자면, 일단 현 상태에서 터질 수 있는거 다 터뜨리고 아래로 전부 내리고, 연속 횟수(답) 저장하는 변수 값을 1 증가시켜줬다. 

 

코드

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

char arr[12][6];
vector<pair<int, int>> dyx = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
bool flag = 0;

void bfs(int y, int x, char c) {
	//cout << "bfs: " << y << " " << x << " " << c << endl;
	int cnt = 1;
	queue<pair<int, int>> q;
	bool visited[12][6] = { 0 }; // set으로 해도 괜찮을듯? 

	q.push({ y, x });
	visited[y][x] = 1;

	while (!q.empty()) {
		int yy = q.front().first;
		int xx = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int n_y = yy + dyx[i].first;
			int n_x = xx + dyx[i].second;

			if (n_y < 0 || n_y >= 12 || n_x < 0 || n_x >= 6) continue; // 범위 밖

			if (arr[n_y][n_x] == c && visited[n_y][n_x] == 0) {
				cnt++;
				q.push({ n_y, n_x });
				visited[n_y][n_x] = 1;
				//cout << "push: " << n_y << " " << n_x << endl;
			}

		}
	}

	if (cnt >= 4) { // 연속된게 4개 이상(마지막에 하나 더 계산됨) -> 터뜨려
		flag = 1;

		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (visited[i][j] == 1) arr[i][j] = '.';
			}
		}

		// 터진 후 파악
		/*cout << "x터진 후: ----------------------------------------" << endl;
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}*/

	}
}

void make_down() {
	// 중력으로 빈공간이 생겼다면 위의 내용들 내려
	for (int col = 0; col < 6; col++) { // 각 열에 대해서
		for (int row = 11; row > 0; row--) { // 아래에서 위로 탐색
			if (arr[row][col] == '.') { // 현재 위치가 빈칸이라면
				// 현재 위치 위쪽을 탐색하며 가장 가까운 뿌요를 내려옴
				for (int k = row - 1; k >= 0; k--) {
					if (arr[k][col] != '.') { // 뿌요 발견
						arr[row][col] = arr[k][col]; // 아래로 내림
						arr[k][col] = '.'; // 기존 위치는 빈칸으로
						break; // 현재 칸에 내렸으면 다음 칸 탐색
					}
				}
			}
		}
	}

	// 중력으로 내린 후 파악
	/*
	cout << "내린 후: ----------------------------------------" << endl;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	*/
}



int main() {

	// 12*6 필드 입력받기
	for (int i = 0; i < 12; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 6; j++) {
			arr[i][j] = str[j];
		}
	}

	// 현 상황에서 터뜨릴 수 있는거 떠뜨리고(.으로 바꾸고) 내리고 반복하기
	int ans = 0;

	while (true) {
		flag = 0;
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (arr[i][j] != '.') bfs(i, j, arr[i][j]);
			}
		}

		if (flag == 0) break; // 터진게 없다. 
		else {
			ans++;
			make_down(); // 중력으로 떨어뜨리기
		}

	}

	cout << ans << endl;

}