[BOJ 6080 // C++] Bad Grass

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

 

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

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

6080번: Bad Grass

주어지는 2차원 배열에서 0이 아닌 수가 이루는 connected component의 개수를 세는 문제이다. 이 때, 이 문제에서는 상하좌우 및 대각선방향의 8방향의 두 칸이 0이 아닐 때 두 칸이 연결되어있다고 한다는 점에 유의하자.

 

아래의 구현의 dr 및 dc와 같은 배열을 이용한 그래프 탐색을 이용해 connected component의 개수를 세어 문제를 해결하자. 글쓴이는 BFS를 이용하였다.

 

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

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

int R, C;
int board[1000][1000];
int ans;

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

void bfs(int sR, int sC) {
	board[sR][sC] = 0;
	queue<pair<int, int>> que;
	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 < 8; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 0) continue;
			board[rr][cc] = 0;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

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

	cout << ans;
}