[백준 BOJ][C++]1012번 유기농 배추: BFS/DFS

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

1012번: 유기농 배추

 

 이 문제는 BFS 또는 DFS로 해결할 수 있습니다. 

 

 먼저 배추밭을 나타낼 2차원 배열 map[][]과 각 배추의 방문 표시할 2차원 배열 visit[][]을 n*m 사이즈로 0으로 초기화 합니다.

 각 테스트 케이스마다 배추밭의 모양이 달라지기 때문입니다.

 이 과정을 init()이라는 함수를 따로 정의하여 테스트 케이스마다 호출하겠습니다. 

 

  k개의 배추의 위치를 입력 받으면 map에서 해당 위치에 해당하는 원소를 1로 저장합니다. 

 

 이제 map에서 아직 방문하지 않은 배추가 있다면 bfs()를 호출하여 모든 배추를 방문하도록 합니다. 

 

 이때, bfs()는 서로 연결되어 있는 배추를 모두 방문합니다. bfs()가 호출될 때마다 필요한 지렁이의 개수 cnt가 하나씩 증가하게 됩니다. 

 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

typedef pair<int, int> pp;

int m, n, k;
int map[50][50] = { 0, };
int visit[50][50] = { 0, };
int cnt;

int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };

void init() {
	cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			map[i][j] = 0;
			visit[i][j] = 0;
		}
	}
}

void bfs(int x, int y) {

	pp p;
	queue<pp> q;

	p.first = x;
	p.second = y;

	q.push(p);
	visit[y][x] = 1;

	while (!q.empty()) {
		p = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int tx = p.first + dx[i];
			int ty = p.second + dy[i];

			if (tx < 0 || tx >= m || ty < 0 || ty >= n)
				continue;
			if (map[ty][tx] == 0)
				continue;
			if (visit[ty][tx] == 1)
				continue;

			visit[ty][tx] = 1;
			q.push({ tx, ty });
		}
	}

}

int main(void) {

	int t;
	int x, y;

	cin >> t;

	while (t > 0) {

		cin >> m >> n >> k;

		init();

		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			map[y][x] = 1;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (visit[i][j] == 0 && map[i][j] == 1) {
					bfs(j, i);
					cnt++;
				}
			}
		}

		cout << cnt << endl;

		t--;
	}


	return 0;
}