프로그래머스 17679: 프렌즈4블록 (2018 카카오 공채 1차)

#include <string>
#include <vector>
#include <set>
#include <algorithm> // sort
using namespace std;

bool check(int r, int c, const vector<string> &board) {
	int i, j;
	for (i = 0; i < 2; i++) {
		for (j = 0; j < 2; j++) {
			if (board[r + i][c + j] != board[r][c]) return false;
		}
	}
	return true;
}

void update(set< pair<int, int> > &s, vector<string> &board, int m, int n) {
	int i, j, k;

	for (auto it : s) board[it.first][it.second] = '.';

	for (i = 1; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (board[i][j] == '.') {
				for (k = i; k > 0; k--) {
					if (board[k - 1][j] == '.') break;
					board[k][j] = board[k - 1][j];
					board[k - 1][j] = '.';
				}
			}
		}
	}
	s.clear();
}

int solution(int m, int n, vector<string> board) {
	int answer = 0;
	int i, j;
	set< pair<int, int> > s; // 지울 블록들의 좌표

	while (true) {
		int cnt = 0; // 현재 라운드에서 지워지는 블록의 수

		for (i = 0; i < m - 1; i++) { // 현재 라운드에서 지워야 할 블록 구하기
			for (j = 0; j < n - 1; j++) {
				if (board[i][j] != '.' && check(i, j, board)) { // insert to set
					s.insert({ i, j });
					s.insert({ i, j + 1 });
					s.insert({ i + 1, j });
					s.insert({ i + 1, j + 1 });
				}
			}
		}

		cnt += s.size();
		answer += cnt;
		if (cnt == 0) break; // 더이상 지울 블록이 없으면 종료

		update(s, board, m, n); // 판 업데이트

	}
	return answer;
}