[백준 1012] 유기농 배추 C++ (bfs, dfs)

 

BFS, DFS를 이용하는 탐색문제인 유기농 배추입니다.

저는 BFS를 이용하며 풀었지만, DFS역시 사용 가능합니다.

테스트 케이스 방식의 입력을 받기 때문에 각각의 테스트 케이스마다 배열을 초기화 해주는 부분이 필요로 합니다.

풀이

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> p;

queue<p> q;

int n, m, k;
int map[51][51];
int visited[51][51];
int cross_x[] = {0, 0, -1, 1};
int cross_y[] = {1, -1, 0, 0};

void bfs(int x, int y)
{
    visited[x][y] = 1;
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int dx = x + cross_x[i];
            int dy = y + cross_y[i];
            if (0 <= dx && 0 <= dy && dx < n && dy < m)
                if (!visited[dx][dy] && map[dx][dy])
                {
                    q.push(make_pair(dx, dy));
                    visited[dx][dy] = 1;
                }
        }
    }
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int cnt = 0;
        memset(visited, 0, sizeof(visited));
        memset(map, 0, sizeof(map));
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0; i < k; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            map[y][x] = 1;
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!visited[i][j] && map[i][j])
                {
                    q.push(make_pair(i, j));
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
}