백준 1012번 유기농 배추( C++ )

문제

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

1012번: 유기농 배추

 

해설

몇개의 그룹이 있는지 맞추는 문제라 bfs, dfs 모두 사용 가능 => 조금 더 간단한 dfs로 구현

여러번 반복하는 문제의 경우 fill을 통해 내부 값을 0으로 초기화 시켜줌

코드

#include <bits/stdc++.h>
using namespace std;
const int box = 54;
int t, m, n, k, x, y, ret;
int mp[box][box];
int visited[box][box];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
void dfs(int y, int x)
{
  visited[y][x] = 1;
 
  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= m || ny >= n || visited[ny][nx] == 1 || mp[ny][nx] == 0)
      continue;
    dfs(ny, nx);
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> t;
 
  for (int p = 0; p < t; p++)
  {
    fill(&mp[0][0], &mp[0][0] + 54 * 54, 0);
    fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
    ret = 0;
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++)
    {
      cin >> x >> y;
      mp[y][x] = 1;
    }
 
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (mp[i][j] == 1 && visited[i][j] == 0)
        {
          dfs(i, j);
          ret++;
        }
      }
    }
    cout << ret << "\n";
  }
}