[BOJ] 11559번 : Puyo Puyo

1. problem : 

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

 

2. solution 1 :

// source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/11559.cpp
#include <bits/stdc++.h>
using namespace std; 

bool ispuyo; 
bool vis[12][6];
string board[12]; 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; 
int ans;
void resetvis() {
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			vis[i][j] = false;
		}
	}
}
void puyo(int x, int y) {
	vector<pair<int, int>> trash; 
	queue<pair<int, int>> Q; 
	vis[x][y] = true; 
	char color = board[x][y];
	Q.push({x,y}); 
	trash.push_back({ x,y }); 
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir]; 
			int ny = cur.second + dy[dir]; 
			if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue; 
			if (vis[nx][ny] || board[nx][ny] == '.' || board[nx][ny] != color) continue; 
			vis[nx][ny] = true; 
			trash.push_back({ nx,ny });
			Q.push({ nx,ny });
		}
	}
	if (trash.size() >= 4) {
		ispuyo = true;
		for (auto cur : trash) {
			board[cur.first][cur.second] = '.';
		}
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	for (int i = 0; i < 12; i++) {
		cin >> board[i];
	}

	do {
		ispuyo = false;
		for (int i = 0; i < 6; i++) {
			int idx = 11;
			for (int j = 11; j >= 0; j--) {
				if (board[j][i] == '.') continue;
				board[idx--][i] = board[j][i];
			}
			while (idx >= 0) board[idx--][i] = '.';
		}
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (board[i][j] != '.' && !vis[i][j]) {
					puyo(i, j);
				}
			}
		}
		if (ispuyo) {
			ans++;
		}
		resetvis();

	} while (ispuyo);
	cout << ans;
}

밑으로 내려가게 하는 함수를 위와 같이 구현할 수도 있다. 또한, 아래와 같이도 구현할 수 있다. 

void gravity() {
    for (int col = 0; col < 6; col++) {
        int idx = 11;
        for (int row = 11; row >= 0; row--) {
            if (board[row][col] != '.') {
                swap(board[row][col], board[idx][col]);
                idx--;
            }
        }
    }
}