[백준] 1012번 유기농 배추

문제: 1012번: 유기농 배추

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int m, n, k; // m: 가로길이, n: 세로길이, k: 배추 위치 개수
        cin >> m >> n >> k;

        vector<vector<int>> board(n);
        vector<vector<int>> visit(n);
        for (int i = 0; i < n; i++) {
            board[i] = vector<int>(m);
            visit[i] = vector<int>(m);
        }

        while (k-- > 0) {
            int x, y;
            cin >> x >> y;
            board[y][x] = 1;
        }

        int dx[4] = { -1, 0, 1, 0 };
        int dy[4] = { 0, -1, 0, 1 };
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 0 || visit[i][j] == 1) continue;

                cnt++; // 배추흰지렁이 수 +1 해주기
                queue<pair<int, int>> nexts;
                nexts.push(make_pair(i, j));
                visit[i][j] = 1;

                while (!nexts.empty()) {
                    pair<int, int> cur = nexts.front();
                    nexts.pop();

                    for (int c = 0; c < 4; c++) {
                        int ny = cur.first + dy[c];
                        int nx = cur.second + dx[c];

                        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                        if (visit[ny][nx] == 1 || board[ny][nx] == 0) continue;

                        nexts.push(make_pair(ny, nx));
                        visit[ny][nx] = 1; // 방문 표시
                    }
                }
            }
        }
        cout << cnt << "\n";
    }
   
    return 0;
}

 

음.. 개인적으로 1926번 문제랑 별반 다를바가 없어서 쉽게 풀렸다. 그냥 BFS 원리 잘 이해만 하고 있으면 별 다른 생각 없이 쉽게 풀 수 있을 것같은 문제였다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS