BOJ 1012 : 유기농 배추

BFS/DFS를 사용하는 문제.

BFS를 사용하였다.

입력을 받은 후 전체 맵을 탐색하면서 배추가 있는 부분부터 BFS를 사용하여 배추 한 덩어리를 찾고, 한 덩어리당 배추흰지렁이 갯수를 늘리면 된다.

 

BFS를 사용하는 것은 동일하지만, 좌표를 큐에 넣어야 하기때문에 pair를 사용한다.

또한 좌표가 맵을 벗어나지 않도록 조건을 넣어주어야 한다.

 

<전체 코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
 
using namespace std;
 
queue<pair<int,int>> q;
int T,m,n,k;
int cnt;
int map[50][50];
int his[50][50];
 
int my[4] = {-1,+1,0,0}; //위 아래 왼 오
int mx[4] = {0,0,-1,+1};
 
void BFS(int y, int x){
    his[y][x] = 1; // 방문 표시
    q.push(make_pair(y, x)); //삽입
    
    while(!q.empty()){
        pair<int, int> tem = q.front();
        q.pop();
        for(int i = 0; i<4; i++){
            if(tem.first+my[i] >=0 && tem.first+my[i]<n && tem.second+mx[i] >=0 && tem.second+mx[i]<m){
                if(map[tem.first+my[i]][tem.second+mx[i]] == 1 && his[tem.first+my[i]][tem.second+mx[i]] == 0){
                    his[tem.first+my[i]][tem.second+mx[i]] = 1; // 방문
                    pair<int, int> _tem = make_pair(tem.first+my[i], tem.second+mx[i]);
                    q.push(_tem);
                }
            }
            
        }
    }
}
 
int main(){
    cin>>T;
    
    
    for(int t = 0; t<T; t++){
        
        memset(map, 0, sizeof(map));
        memset(his,0,sizeof(his));
        cnt = 0;
        
        cin>>m>>n>>k;
        for(int i = 0; i<k; i++){
            int x,y;
            cin>>x>>y;
            map[y][x] = 1;
        }
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(map[i][j] == 1 && his[i][j] == 0){
                    BFS(i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
  
}