백준 1012번: 유기농 배추

[문제 링크]

1012번: 유기농 배추

---

간단한 그래프 탐색 문제였다.

그래프를 탐색하면서 배추가 있는 땅을 시작으로 하는 bfs를 수행하고 인접해 있는 배추를 방문 표시한다.

모든 좌표를 탐색했을 때 bfs 호출 횟수가 지렁이의 마리 수가 된다.

---

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

// M: 가로길이(x), N: 세로길이(y), K: 배추가 심어진 개수
int M, N, K;
bool adj[50][50];
bool visited[50][50];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
			}
		}
	}
}

void dfsStack(int startY, int startX) {
	stack<Pos> stk;
	stk.push({ startY, startX });
	visited[startY][startX] = true;

	while (!stk.empty()) {
		int hereY = stk.top().y;
		int hereX = stk.top().x;
		stk.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					stk.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

void dfsRecursion(int startY, int startX) {
	visited[startY][startX] = true;

	for (int i = 0; i < 4; i++) {
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];

		if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
			if (adj[nextY][nextX] && !visited[nextY][nextX]) {
				dfsRecursion(nextY, nextX);
			}
	}
}

int graphSearchAll() {
	int result = 0;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			if (adj[y][x] && !visited[y][x]) {
				result++;
				bfs(y, x);
				//dfsStack(y, x);
				//dfsRecursion(y, x);
			}
		}

	return result;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		cin >> M >> N >> K;

		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		while (K--) {
			int x, y;
			cin >> x >> y;
			adj[y][x] = true;
		}

		cout << graphSearchAll() << endl;
	}

	return 0;
}