BOJ[백준] - 1012 - 유기농배추

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

 

 

DFS 또는 BFS로 풀면 될 것 같습니다.

BFS를 쓰면 방문여부만으로도 해결이 되는 문제입니다. 그런걸보면 flood fill 느낌이 나네요..

 

 

1. DFS 입니다.

 

#include <stdio.h>
char land[52][52];
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
 
void dfs(int x, int y)
{
  if (!land[x][y]) return;
  land[x][y] = 0;
  for (int i=0; i<4; i++)
    dfs(x+dx[i], y+dy[i]);
}
int main(void)
{
  int T;
  scanf("%d",&T);
  while (T--)
  {
    int m,n,k;
    scanf("%d %d %d", &m, &n, &k);    
    while(k--)
    {
      int x, y;
      scanf("%d %d", &x, &y);
      land[y+1][x+1] = 1;
    }
    int Needed = 0;
    for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
        if (land[i][j])
        {
          dfs(i,j);
          Needed++;
        }
    printf("%d\n", Needed);
  }
  return 0;
}

 

 

 

2.  BFS 입니다.

 

가독성을 위해 아래처럼 코드를 짰지만, 사실 enqueue나 dequeue는 따로 함수로 둘 필요없죠 ㅋ

 

#include <cstdio>
 
#define MAX_NUM        (52)
 
typedef struct { int x; int y; } PAIR;
int head, tail, Needed;
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
PAIR queue[(MAX_NUM * MAX_NUM)];
char land[MAX_NUM][MAX_NUM];
 
void enqueue(PAIR t)
{
    queue[head++] = t;
    head = head % MAX_NUM;
}
 
PAIR dequeue()
{
    PAIR t = queue[tail++];
    tail = tail % MAX_NUM;
    return t;
}
 
void BFS(PAIR p)
{
    int tx, ty;
    enqueue(p);
    while (head != tail)
    {
        PAIR p2 = dequeue();
        tx = p2.x, ty = p2.y;
        for (int i = 0; i<4; i++)
            if(land[tx + dx[i]][ty + dy[i]])
                land[tx + dx[i]][ty + dy[i]] = 0, enqueue({ tx + dx[i], ty + dy[i] });
    }
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int m, n, k;
        scanf("%d %d %d", &m, &n, &k);
        while(k--)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            land[y+1][x+1] = 1;
        }
        head = tail = Needed = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (land[i][j])
                {
                    land[i][j] = 0;
                    BFS({ i, j });
                    Needed++;
                }
            }
        }
        printf("%d\n", Needed);
    }
    return 0;
}