[Silver II] 유기농 배추 - 1012

[Silver II] 유기농 배추 - 1012

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

DFS를 이용해서 풀게 된 문제입니다.

코드는 생각보다 쉽게 완성되었는데 테스트 케이스로 여러 개의 그래프를 확인 후 출력하는 문제여서 기준이 되는 그래프 배열과 방문 여부 배열을 초기화해줘야 하는 부분에서 약간 시간이 소요됐습니다.

[Silver II] 유기농 배추 - 1012 - 풀이코드

그래프와 방문여부를 초기화하는 부분

for (int i = 0; i < t; i++)
{
	fill(&a[0][0], &a[max_n - 1][max_n], 0);
	fill(&visited[0][0], &visited[max_n - 1][max_n], 0);
	testCase();
}

전체 코드

#include <bits/stdc++.h>
using namespace std;

const int max_n = 54;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int t, m, n, a[max_n][max_n], y, x, ny, nx, k;
vector<int> retV;
bool visited[max_n][max_n];

void dfs(int y, int x) 
{
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
		if (a[ny][nx] == 1 && !visited[ny][nx]) 
		{
			dfs(ny, nx);
		}
	}
	return;
}

void testCase()
{
	int ret = 0;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> x >> y;
		a[y][x] = 1;
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 1 && !visited[i][j])
			{
				ret++; 
				dfs(i, j);
			}
		}
	}
	
	retV.push_back(ret);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> t;
	
	for (int i = 0; i < t; i++)
	{
		fill(&a[0][0], &a[max_n - 1][max_n], 0);
		fill(&visited[0][0], &visited[max_n - 1][max_n], 0);
		testCase();
	}
	
	for (int i : retV) cout << i << '\n';
		
	return 0;
}