백준 1012번 유기농 배추 [C++]

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

1012번: 유기농 배추

#문제 간단 정리

 

#문제 해결 방법

그래프를 이용한 탐색 구현 문제이다.

 

주요 로직은 양배추가 있는 x y 좌표들만 따로 저장해서

양배추들 좌표들만 따로 순회를 해주는데

만약 이전에 접근한 적이 없다면 

counting 전역변수로 새로운 진입을 카운팅 해준다.

여러모로 전역변수를 쓰면 편하다

 

#전체 코드

#include <iostream>
#include <vector>
using namespace std;

int M, N, K;
int counting;

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

void dfs(vector<vector<int>> &map, vector<vector<bool>> &check ,int x, int y) {
    
    check[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
            if (map[nx][ny] == 1 && check[nx][ny] == false) {
                dfs(map, check, nx, ny);
            }
        }

    }

}

int main() {
    

    int T;
    cin >> T;

    while (T--) {
        counting = 0;
        cin >> M >> N >> K;
        vector<vector<int>> map(M, vector<int>(N, 0));
        vector<vector<bool>> check(M, vector<bool>(N, false));
        vector<pair<int, int>> cabbages;

        for (int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;

            map[x][y] = 1;
            cabbages.push_back({ x,y });
        }

        for (pair<int, int> a : cabbages) {
            if (check[a.first][a.second] == false) {
                counting++;
                dfs(map, check, a.first, a.second);
            }
        }
        cout << counting << '\n';
    }



    return 0;
}