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

문제: www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

 

문제풀이

 

흰 배추 지렁이는 인접한 배추로 이동할 수 있으므로 서로 인접한 배추가 몇 군데 있는지를 알아내는 문제였다.

 

BFS를 이용하여 방문하지 않은 배추를 찾을 때마다 카운트를 증가시켜 서로 인접한 배추가 몇 군데 있는지를 알아냈다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

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


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

    int t;
    cin>>t;

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

        while(k--){
            int x,y;
            cin>>x>>y;

            board[x][y] = 1;
        }

        queue<pair<int,int>> q;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(vistited[i][j] || !board[i][j]) continue; //이미 방문한 배추이거나 배추가 아니면 continue
                q.push({i,j});
                vistited[i][j] = 1;
                cnt++; //새로운 영역을 찾았으므로 카운트

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

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

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

                        vistited[nx][ny] = 1;
                        q.push({nx,ny});
                    }
                }
                
            }
        }

        cout<<cnt<<"\n";

        for(int i=0; i<m; i++){ //다음 테스트케이스를 위해 board와 visited를 초기화
            fill(board[i], board[i]+n, 0);
            fill(vistited[i], vistited[i]+n, 0);
        }
    }

    return 0;
}

 

 

결과