BOJ 1012 유기농 배추 DFS

- DFS + cnt 구하기

- 기본적인 문제. 섬의 갯수(BOJ 4963)와 매우 유사한 문제

 

 

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

 

#include <iostream>
#include <cstdio>
using namespace std;

int field[55][55]; // 배추 밭
int visited[55][55];
int m,n;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

//DFS
void dfs(int x, int y, int cnt){
  visited[x][y]=cnt;
  for(int i=0; i<4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx>=0 && nx<n && ny>=0 && ny<m){
      if(field[nx][ny]==1 && visited[nx][ny]==0){
        dfs(nx, ny, cnt);
      }
    }
  }
}

int main(){
  int testcase;
  int cabbage=0;
  scanf("%d", &testcase);

  while (testcase--) {
    scanf("%d %d %d", &m, &n, &cabbage);
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        field[i][j]=0;
        visited[i][j]=0;
      }
    } //사용할 배열 초기화

    for(int i=0; i<cabbage; i++){
      int temp1, temp2;
      scanf("%d %d", &temp1, &temp2);
      field[temp2][temp1] = 1;
    } //배추 심기 완료 (input)

    int cnt = 0;
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(field[i][j]==1 && visited[i][j]==0)
          dfs(i,j, ++cnt);
      }
    }
   printf("%d", cnt);
  }
}