[BOJ 11123 // C++] 양 한마리... 양 두마리...

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

 

이번에 볼 문제는 백준 11123번 문제인 양 한마리... 양 두마리...이다.
문제는 아래 링크를 확인하자.

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

11123번: 양 한마리... 양 두마리...

주어진 격자판의 '#'을 노드로, 인접한 '#'끼리의 관계를 에지로 모델링한 그래프의 connected component의 개수를 세는 문제이다.

 

connected component의 개수는 dfs, bfs등의 그래프탐색이나 disjoint set 등을 이용해 셀 수 있다. 글쓴이는 bfs를 이용해 문제를 해결하였다.

 

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

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

int T;
int R, C;
string board[100];
int visited[100][100];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

queue<pair<int, int>> que;

void bfs(int sR, int sC) {
	visited[sR][sC] = 1;
	que.push(make_pair(sR, sC));

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] == '#' && !visited[rr][cc]) {
				visited[rr][cc] = 1;
				que.push(make_pair(rr, cc));
			}
		}
	}
}

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

	cin >> T;
	while (T--) {
		int ans = 0;
		memset(visited, 0, sizeof(visited));
		cin >> R >> C;
		for (int r = 0; r < R; r++) cin >> board[r];

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r][c] == '#' && !visited[r][c]) {
					ans++;
					bfs(r, c);
				}
			}
		}

		cout << ans << '\n';
	}
}