1012 유기농 배추

오늘의 기분 좋은 일 : 이제 bfs / dfs 편하고 빠르게 짤 수 있다!

 

딱 보자마자 dfs 쓰면 되겠다 싶었다. 

 

더 자세히 적으면 배열이 주어지고 배열의 칸을 연달아 체크하면서 1의 개수를 구해야 하고 또 1의 집합의 개수를 구해야 하니깐 bfs를 여러번 돌리면 되겠다 싶었음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int n, m;
int maps[55][55];
bool visited[55][55];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void dfs(int y, int x)
{
    visited[y][x] = true;

    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] < 0 || m <= x + dx[i])
            continue;
        if (y + dy[i] < 0 || n <= y + dy[i])
            continue;

        if (maps[y + dy[i]][x + dx[i]] == 0)
            continue;

        if (visited[y + dy[i]][x + dx[i]])
            continue;

        dfs(y + dy[i], x + dx[i]);
    }
}

void solve()
{
    int k;
    cin >> m >> n >> k;

    memset(maps, 0, sizeof(maps));
    memset(visited, false, sizeof(visited));

    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        maps[y][x] = 1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (maps[i][j] == 0 || visited[i][j])
                continue;
            dfs(i, j);
            ans++;
        }
    }
    
    cout << ans << endl;
}

int     main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        solve();
    }

    return 0;
}

 

테스트 케이스가 주어진 문제는 저렇게 solve() 함수로 따로 빼서 구하는 게 좋다. 훨~~~ 깔끔함

 

미세 팁인데 컴파일 에러가 뜬 경우 이거 누르면 어느 부분에서 틀린지 알려준다.

 

내가 memset함수를 사용했는데 cstring이 없어서 문제였다. 오..