BaekJoon 1012번: 유기농 배추(C++ DFS/BFS)

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

1012번: 유기농 배추

풀이법

1) DFS와 BFS를 이용해서 풀 수 있는 문제이다.

2) 최소의 벌레의 개수를 찾아야 하니, visited 배열을 이용한다면 쉽게 문제를 해결할 수 있다.

3) 한번 방문한 노드를 다시 방문하지 않으므로 시간 복잡도는 O(nm)이 될 것이다

 

재귀를 이용한 DFS를 이용한 풀이

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

int t;
int arr[51][51];
bool check[51][51];
int m, n, k;
int temp;
vector<int> ans;

int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };

void dfs(int x, int y)
{
	temp++;
	check[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int va = x + vx[i];
		int vb = y + vy[i];
		if (va < 0 || va >= m || vb < 0 || vb >= n)
		{
			continue;
		}
		if (arr[va][vb]==1 && !check[va][vb])
		{
			dfs(va, vb);
		}
	}
}

int main()
{
	cin.tie(0);
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		cin >> n >> m >> k; //열 행 심은 위치 개수 들어옴
		for (int i = 0; i < k; i++)
		{
			int a, b;
			cin >> b >> a;
			arr[a][b] = 1;
		}

		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (arr[i][j] == 1 && !check[i][j])
				{
					temp = 0;
					dfs(i, j);
					ans.push_back(temp);
				}
			}
		}
		cout << ans.size() << "\n";
		memset(arr, 0, sizeof(arr));
		memset(check, 0, sizeof(check));
		ans.clear();
	}
	//
}

Queue를 이용한 BFS 풀이

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
using namespace std;

int m,n,k,t;
int arr[51][51];
bool visited[51][51];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,-1,1,0 };

int bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x,y });
	while (!q.empty())
	{
		int bx = q.front().first;
		int by = q.front().second;
		q.pop();
		if (visited[bx][by] == true)
			continue;
		visited[bx][by] = true;
		for (int i = 0; i < 4; i++)
		{
			int dx = bx + vx[i];
			int dy = by + vy[i];
			if (dx<0 || dx>=m || dy<0 || dy>=n)
				continue;
			if (arr[dx][dy] == 1 && !visited[dx][dy])
				q.push({ dx,dy });
		}
	}
	return 1;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		cin >> m >> n >> k;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				arr[i][j] = 0;
				visited[i][j] = false;
			}
		}
		for (int i = 0; i < k; i ++)
		{
			int a, b;
			cin >> a >> b;
			arr[a][b] = 1;
		}
		int cnt = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (arr[i][j] == 1 && !visited[i][j])
				{
					cnt += bfs(i, j);				
				}
			}
		}
		cout << cnt << "\n";
	}

}