[백준 1012] 유기농 배추 (BFS)

문제출처: https://www.acmicpc.net/problem/1012

BFS를 이용한 풀이입니다. DFS를이용한 풀이는 링크를 참조해주세요. https://jow1025.tistory.com/88

풀이

배추흰지렁이의 최소 수는 문제에도 힌트가 있는데, 배추가 있는 부분의 영역의 갯수입니다. 말로하면 헷갈릴 수 있으니 아래 그림을 참고해주세요.

즉, 배추흰지렁이의 최소 수는 bfs or dfs연산의 횟수(조건에 맞게 돌렸을 때), 즉 배추의 요소의 갯수라고 할 수 있습니다. 좌표가 헷갈릴 수 있으니 그것만 주의하시면 되고, 다른것은 어렵지않으므로 설명은 소스코드로 대체하겠습니다.

코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int map[50][50];
int check[50][50];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int m, n, k;
//가로, 세로,배추위치갯수
void bfs(int y,int x);
int main()
{
	int t;
	cin >> t;
	int x, y;
	while (t--)
	{
		memset(map, 0, sizeof(map));
		memset(check, 0, sizeof(check));
		cin >> m >> n >> k;
		int ans = 0;
		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 (map[i][j] == 1 && check[i][j] == 0)
				{
					bfs(i, j);
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
}
void bfs(int y, int x)
{
	check[y][x] = 1;
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	while (!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && nx >= 0 && nx < m && ny < n) {
				if (map[ny][nx] == 1 && check[ny][nx] == 0)
				{
					q.push({ ny,nx });
					check[ny][nx] = 1;
				}
			}
		}
	}
	
}

결과