문제 출처

1. 문제설명


  • 우리가 알고 있는 뿌요뿌요 게임과 매우 비슷하다.
  • 상,하,좌,우로 인접한 뿌요가 같은색이면서 4칸이상 연속으로 배치되어 있다면 터진다.
    • 터질 때를 1연쇄라고 한다.
  • 처음 뿌요는 항상 아래쪽에 배치되어 있다.



2. 알고리즘 설계


  • BFS 또는 DFS로 뿌요를 확인하고, 터트리는..
  • 그래프 문제이면서, 시뮬레이션 문제이다.
  • 터트리는 구현
    • 본인은 BFS를 이용하였다.
    • BFS로 같은 색이라면 전진하면서 큐에 담는다. 동시에 임시 벡터에도 담는다.
    • 탐색이 끝났다면, 임시 벡터의 크기가 4 이상인지 확인하고 .으로 변경한다.
    for (pii pos : tmp)
      board[pos.Y][pos.X] = '.';
    
  • 뿌요의 위치를 옮겨주는 기능
    • 뿌요가 터졌다면, 아래로 떨어지게 된다.
    • 높이 H가 되거나 .이 아닌 지점까지 내려주면 된다.
    while (tmp + 1 < H && board[tmp + 1][i] == '.') {
      swap(board[tmp][i], board[tmp + 1][i]);
      tmp++;
    }
    



3. 전체 코드


#include <bits/stdc++.h>
#define Y first
#define X second
using namespace std;
using pii = pair<int, int>;

const int W = 6, H = 12;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

bool chk, vis[H][W];
string board[H];

void explode(int y, int x) {
	queue<pii> q;
	vector<pii> tmp;

	q.push({ y, x });
	tmp.push_back({ y,x });
	vis[y][x] = true;

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

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];

			if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
			if (vis[ny][nx] || board[ny][nx] != board[cur.Y][cur.X]) continue;

			q.push({ ny,nx });
			tmp.push_back({ ny,nx });
			vis[ny][nx] = true;
		}
	}

	if (tmp.size() >= 4) {
		chk = true;

		for (pii pos : tmp)
			board[pos.Y][pos.X] = '.';
	}
}

void drop() {
	for (int i = 0; i < W; i++) {
		for (int j = H - 2; j >= 0; j--) {
			int tmp = j;
			while (tmp + 1 < H && board[tmp + 1][i] == '.') {
				swap(board[tmp][i], board[tmp + 1][i]);
				tmp++;
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < H; i++)
		cin >> board[i];

	int ans = 0;

	do {
		fill_n(&vis[0][0], H * W, false);
		chk = false;
		drop();

		for (int i = 0; i < H; i++) 
			for (int j = 0; j < W; j++) 
				if (!vis[i][j] && board[i][j] != '.')
					explode(i, j);

		if (chk) ans++;

	} while (chk);
	
	cout << ans;
	return 0;
}



4. 소감


  • 코드를 보면 알 수 있듯이, swap()은 내가 구현한 게 아니다.
  • 헤더파일 <algorithm>에 구현되어 있다.
  • 일부 범위를 바꾸는 swap_ranges()라는 함수도 있다.
  • 자세한 내용은 여기를 참고해주세요!