[BOJ] 백준 1012번 유기농 배추 (C++ 코드)

🧨 백준 1012번 - 유기농 배추

문제 난이도 : 실버2

문제 링크 : www.acmicpc.net/problem/1012

1012번: 유기농 배추

🧨 알고리즘 선택 및 C++ 코드

2178번 미로탐색 문제와 비슷하게 2차원 좌표를 이용해 위치 이동을 해야하므로 상하좌우 dx, dy 배열을 사용했다. 재귀를 사용하는 DFS는 뭔가 거부감이 있어서 일단 BFS로 구현했다. (DFS로 짜도 상관없는 거 같다) 처음에 대체 어디에 배추가 있는지 알아야 지렁이를 놓든 말든 할거 아닌가 싶어서 이를 표시해주는 리스트를 만들어볼까 했는데, 내가 원하는대로 구현이 불가능했다. 어쩔 수 없이 N * M 크기의 밭을 반복문으로 모두 체크하는 방법밖에 없어서.. 그렇게 했는데 시간초과 안 난 걸 보니 이게 맞는 거 같다 ?

그리고 BFS를 쓰긴 했지만 큐에 들어가있는지를 체크하는거나 isMarked 뭐 그런게 필요가 없었다. 근데도 돌아간다. 없어도 되는 구조이긴 한데 참 애매하다. 다른 친구들 코드를 봐야겠다..

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

int T, M, N, K;
int dx[] = { -1, 1, 0, 0 }; // 좌, 우, 상, 하
int dy[] = { 0, 0, -1, 1 };

void BFS(int G[50][50], int y, int x) {
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	while (!q.empty()) {
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur_x + dx[i];
			int ny = cur_y + dy[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (G[nx][ny] == 0) continue;
			if (G[nx][ny] == 1) {
				G[nx][ny] = 0;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

int main(void) {
	cin >> T;

	for (int t = 0; t < T; t++) {
		cin >> M >> N >> K;
		int G[50][50] = { 0 };
		for (int i = 0; i < K; i++) {
			int m, n;
			cin >> m >> n;
			G[n][m] = 1;
		}

		int count = 0;
		for (int x = 0; x < M; x++) {
			for (int y = 0; y < N; y++) {
				if (G[y][x] == 0) continue;
				else {
					BFS(G, y, x);
					count++;
				}
			}
		}
		cout << count << '\n';
	}

	return 0;
}