문제

입력

입출력 예시

코드

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

int N, K, Q;
vector<vector<char>> adj;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int x, int y) {
	char c = adj[x][y];
	queue<pair<int, int>> q;
	vector<vector<int>> visit(N + 1, vector<int>(N + 1, 0));
	vector<pair<int, int>> same;
	q.push({x, y});
	same.emplace_back(make_pair(x, y));
	visit[x][y] = 1;
	
	while(!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nextx = nowx + dx[i];
			int nexty = nowy + dy[i];
			if(nextx >= 1 && nextx <= N && nexty >= 1 && nexty <= N){
				if(c == adj[nextx][nexty] && !visit[nextx][nexty]) {
					q.push({nextx, nexty});
					same.emplace_back(make_pair(nextx, nexty));
					visit[nextx][nexty] = 1;
				}
			}
		}
	}
	if(same.size() >= K) {
		for(pair<int, int> p : same) 
			adj[p.first][p.second] = '.';
	}
}

int main() {
	cin >> N >> K >> Q;
	adj = vector<vector<char>>(N + 1, vector<char>(N + 1, '.'));
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++) 
			cin >> adj[i][j];
	}
	for(int i = 0; i < Q; i++) {
		int a, b;
		char c;
		cin >> a >> b >> c;
		adj[a][b] = c;
		bfs(a, b);
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++) {
			printf("%c", adj[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Q의 최대가 1000으로 많지 않아서, 입력받을 때마다 bfs를 실행하는게 가능하다.

bfs 에서는 현재 입력받은 칸을 기준으로 상하좌우의 문자가 현재 칸과 같은지 확인하며 bfs를 진행한다. 평소 bfs와 한 가지 다른 점은 same이라는 vector<pair<int, int>> 형의 배열에 입력받은 칸의 문자와 같은 칸의 좌표를 저장한 후, bfs가 끝난 뒤에 same의 크기가 K보다 크거나 같은 경우 연결 요소를 제거해준다.