취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 12051번 문제인 Dynamic Grid (Large)이다.
문제는 아래 링크를 확인하자.

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

주어지는 격자의 칸의 수가 10000 이하이고, 서로 연결된 칸의 쌍의 개수는 40000 이하이고, connected region의 수를 세야 하는 횟수는 많아야 10000회임을 관찰하자. 따라서 제한시간이 5초로 널널함을 이용하면, connected region의 수를 구하는 쿼리가 주어질 때마다 매번 격자 전체를 살펴도 문제를 충분히 해결할 수 있음을 관찰할 수 있다.

아래는 제출한 소스코드이다.

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

int R, C, Q;
char board[100][100];
int visited[100][100];
queue<pair<int, int>> que;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void bfs() {
	int ans = 0;
	memset(visited, 0, sizeof(visited));
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == '1' && !visited[r][c]) {
				que.push(make_pair(r, c));
				visited[r][c] = 1;
				while (!que.empty()) {
					int rr = que.front().first, cc = que.front().second; que.pop();
					for (int i = 0; i < 4; i++) {
						int rrr = rr + dr[i], ccc = cc + dc[i];
						if (rrr < 0 || rrr >= R || ccc < 0 || ccc >= C || board[rrr][ccc] == '0' || visited[rrr][ccc]) continue;
						visited[rrr][ccc] = 1;
						que.push(make_pair(rrr, ccc));
					}
				}
				ans++;
			}
		}
	}
	cout << ans << '\n';
}

void solve() {
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}
	cin >> Q;
	while (Q--) {
		char q; cin >> q;
		if (q == 'Q') bfs();
		else {
			int r, c; char x; cin >> r >> c >> x;
			board[r][c] = x;
		}
	}
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ":\n";
		solve();
	}
}