1012: 유기농 배추

✔ 문제 링크

BOJ 1012: 유기농 배추

✔ 문제해결전략

• 그래프 탐색
• BFS(Breadth First Search)
• Flood fill

✔ 해결과정

• 정직하게 BFS 하면 된다.

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int mp[50][50];
int vis[50][50];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t, n, m, k;
    cin >> t;

    while (t--) {
        memset(mp, 0, sizeof(mp));
        memset(vis, 0, sizeof(vis));
        int cnt = 0;
        cin >> m >> n >> k;

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mp[i][j] == 0 || vis[i][j] != 0) continue;
                cnt++;
                vis[i][j] = 1;
                queue < pair < int, int > > q;
                q.push({i, j});

                while (!q.empty()) {
                    pair < int, int > cur = q.front();
                    q.pop();
                    for (int p = 0; p < 4; p++) {
                        int nx = dx[p] + cur.second;
                        int ny = dy[p] + cur.first;
                        if (nx >= m || nx < 0 || ny >= n || ny < 0) continue;
                        if (mp[ny][nx] == 0 || vis[ny][nx] != 0) continue;
                        vis[ny][nx] = 1;
                        q.push({ny, nx});
                    }
                } // while

            } // j
        } // i
        cout << cnt << '\n';
    } // while

}