cpp) 백준 1012: 유기농 배추

Problem

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

1012번: 유기농 배추

 

 

Solution

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int t;             // 테스트케이스 개수
int m, n;          // 배추밭 가로, 세로 길이
int k;             // 배추가 심어진 위치의 개수
bool map[50][50];  // 배추밭


void dfs(int row, int col){
    // 인덱스 범위 초과 예방
    if(row<0||row>=50) return;
    if(col<0||col>=50) return;

    // 이미 검사를 했거나 배추를 심은 땅이 아닌 경우 skip
    if(!map[row][col]) return;

    // 검사 완료(다시 볼 필요 없으므로 0)
    map[row][col]=0;

    //상하좌우
    dfs(row,col+1);
    dfs(row,col-1);
    dfs(row-1,col);
    dfs(row+1,col);
}



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

    cin >> t;
    for(int i=0;i<t;i++){
        cin >> m >> n >> k;
        for(int j=0;j<k;j++){
            int a, b;
            cin >> a >> b;
            map[a][b]=1;  // (a,b) 위치는 배추가 심어져 있음
        }
        int cnt = 0;  // 배추흰지렁이 수 = 정답값
        for(int row=0;row<m;row++){
            for(int col=0;col<n;col++){
                if(map[row][col]==1){
                    cnt++;
                    dfs(row,col);
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

 

 

Reference

https://bconfiden2.tistory.com/109

[백준] 1012.cpp : 유기농 배추