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

백준 1012 : 유기농 배추

난이도 : 실버 2

시간 : 20분 소요

 

 

문제

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

1012번: 유기농 배추

 

풀이 과정

 

이 문제는 2차원 배열을 기준으로 bfs를 해주면 쉽게 풀 수 있다.

먼저 배추가 심어지는 위치를 2차원 배열로 저장한다.

그 후에는 배추가 심어지는 위치를 순차적으로 찾아서 방문처리(0처리)를 하고, 인접해 있는 배추도 방문처리(0처리)를 해준다.

이는 한 마리의 지렁이가 커버할 수 있는 영역을 방문처리해줬다고 생각하면 쉽다.

 

더이상 인접한 배추가 없으면 함수를 빠져나오고, 다시 배추가 심어진 위치를 찾으며 반복한다.

 

 

최종 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace::std;

int T;
int n,m,k;
int cnt;

int ba[51][51];
int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs(int y, int x){
    queue<pair<int, int>> q;
    ba[y][x] = 0;
    cnt++;
    q.push({y,x});
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
       
        for(int i=0; i<4; i++){
            int ny = ty+ud[i];
            int nx = tx+lr[i];
            if(ny>=0 && nx>=0 && ny<=50 && nx<=50){
                if(ba[ny][nx] == 1){
                    ba[ny][nx] = 0;
                    q.push({ny,nx});
                }
            }
        }
        
    }
}

int main(){
    scanf("%d", &T);
    
    for(int i=0; i<T; i++){
        cnt = 0;
        scanf("%d %d %d", &m, &n, &k);
        for(int i=0; i<k; i++){
            int y,x;
            scanf("%d %d", &y, &x);
            ba[y][x] = 1;
        }
        
        for(int y=0; y<=50; y++){
            for(int x=0; x<=50; x++){
                if(ba[y][x] == 1){
                    bfs(y, x);
                }
            }
        }
        printf("%d\n", cnt);
        memset(ba, 0, sizeof(ba));
        
    }
}