취미로 코딩하기

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

이번에 볼 문제는 백준 7873번 문제인 Decision이다.
문제는 아래 링크를 확인하자.

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

주어진 각 격자의 칸은 두 대각선으로 잘라서 보았을 때 상하좌우의 삼각형모양의 네 칸으로 나눌 수 있다. 주어진 입력을 이와 같이 나눈 격자로 읽어 그래프로 모델링하면 주어진 문제는 그래프에서의 connected component의 개수를 세는 문제로 어렵지 않게 변환하여 문제를 해결하자.

그래프로 모델링할 때, 원래 격자에서의 인접한 칸 사이의 연결관계와 각 칸 내부에 생성된 삼각형들 사이의 연결관계를 모두 고려해야 함에 유의하자.

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

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

int R, C;
bool board[1000][1000][4];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
queue<int> que;

void bfs(int sR, int sC, int sD) {
	board[sR][sC][sD] = 0;
	que.push(sR * 1000000 + sC * 1000 + sD);
	while (!que.empty()) {
		int r = que.front() / 1000000, c = que.front() % 1000000 / 1000, d = que.front() % 1000; que.pop();
		for (int dd = 0; dd < 4; dd++) {
			if ((dd ^ d) & 2) {
				if (board[r][c][dd]) {
					board[r][c][dd] = 0;
					que.push(r * 1000000 + c * 1000 + dd);
				}
			}
		}
		int rr = r + dr[d], cc = c + dc[d], dd = d ^ 1;
		if (rr > -1 && rr < R && cc > -1 && cc < C && board[rr][cc][dd]) {
			board[rr][cc][dd] = 0;
			que.push(rr * 1000000 + cc * 1000 + dd);
		}
	}
}

void solve() {
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			char x; cin >> x;
			if (x == 'A');
			else if (x == 'B') board[r][c][2] = 1, board[r][c][1] = 1;
			else if (x == 'C') board[r][c][3] = 1, board[r][c][1] = 1;
			else if (x == 'D') board[r][c][3] = 1, board[r][c][0] = 1;
			else if (x == 'E') board[r][c][2] = 1, board[r][c][0] = 1;
			else board[r][c][3] = 1, board[r][c][2] = 1, board[r][c][1] = 1, board[r][c][0] = 1;
		}
	}
	int ans = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			for (int i = 0; i < 4; i++) {
				if (board[r][c][i]) {
					bfs(r, c, i);
					ans++;
					break;
				}
			}
		}
	}
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}