백준 #1012 유기농 배추

텃밭에 배추가 심어져 있는데, 유기농으로 배추를 기르기 위해서 배추 흰지렁이를 풀어놓고자 합니다.  배추 흰지렁이는 배추가 모여있는 곳에는 한마리만 풀어놓아도, 인접한 배추로 옮겨다니면서 해충을 예방할 수 있습니다.

 

이 문제는 섬의 갯수 문제 등 자주 나오는 문제로, 그래프 이론 중 가장 기초적인 DFS, BFS 알고리즘을 이용해서 해결할 수 있습니다.

 

아래는 백준 사이트의 문제 링크입니다.

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

1012번: 유기농 배추

 

BFS를 이용해도 되고 DFS를 이용해도 됩니다.  둘 다 인접한 모든 곳을 다 순회할 수 있습니다.  개인적으로는 DFS를 선호합니다.  구현하는 것이 훨씬 더 간단해서요.

 

0	0	0	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0
0	0	1	0	0	0	1	1	1	0
0	0	1	0	0	0	0	1	1	0
0	1	1	0	0	0	0	0	0	0
0	0	0	1	1	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0

 

DFS를 이용하든 BFS를 이용하든 시작하는 노드는 어떤 것이 되든 상관이 없습니다.  배열에 데이터가 담겨져 있으면, 순차적으로 검색을 해보면서 배열값이 1이 되어있는 곳에서부터 DFS를 돌면서 배열값을 1이 아닌값으로 대치하는 알고리즘을 사용합니다.  그렇게 하면, 자연스럽게 main() 함수에서 배열에 있는 1을 찾을 때마다 지렁이를 카운팅해주면 됩니다.

 

아래는 제가 짠 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1012 - Organic Cabbage
//    - by Aubrey Choi
//    - created at 2019-08-01
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <memory.h>

void dfs(char v[], int y, int x, int n, int m)
{
  int d[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
  v[y*m+x] = 0;
  for(int i = 0; i < 4; i++)
  {
    int nx = x+d[i][1], ny = y+d[i][0];
    if(nx<0||nx>=m||ny<0||ny>=n||v[ny*m+nx]==0) continue;
    dfs(v, ny, nx, n, m);
  }
}

int main()
{
  int t, m, n, k, x, y;
  char v[2500];
  scanf("%d", &t);
  while(t--)
  {
    int ans = 0;
    scanf("%d%d%d", &m, &n, &k);
    memset(v, 0, m*n);
    while(k--)
    {
      scanf("%d%d", &x, &y);
      v[y*m+x] = 1;
    }
    for(int i = 0; i < m*n; i++)
    {
      if(!v[i]) continue;
      dfs(v, i/m, i%m, n, m);
      ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}