[BFS]백준 1012번 유기농배추

백준 1012번

유기농배추

풀고 보니 좀 복잡하게 푼 감은 있지만, 그래도 전체적으로는 맞는 방향으로 푼 것 같다.

먼저 전체 배추를 좌표쌍 pair로 정리해 묶어 배열로 저장한다.

전체 배열을 순환하며 하나씩 뽑아 그룹장으로 정한다.

그룹장은 자신의 바로 옆에 있는 배추들을 큐에 담는다.

큐에 담긴 배추들은 하나씩 pop 되며 자신의 옆에 있는 배추를 큐에 담는다.

더 이상 큐에 담을 배추가 없어지면 하나의 그룹이 끝난 것으로 판단한다.

그룹에 담긴 배추들 (큐에 담겼던 배추들)은 모두 따로 표시를 해놓고 다음 그룹장을 뽑을 때는 제외한다.

이렇게 하면 그룹의 개수를 구할 수 있다.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <math.h>

using namespace std;

int main(){
    int cases;
    cin >> cases;
    vector<int> answer;
    for(int x=0;x<cases;x++){
        // Handle inputs
        int width, height, cabbage_num;
        cin >> width >> height >> cabbage_num;
        int worms= 0;
        vector<pair<int,int> > cabbages;
        vector<int> visited(cabbage_num,0);
        for(int j=0;j<cabbage_num;j++){
           int x,y;
           cin >> x >> y;
           pair<int,int> pii = make_pair(x,y);
           cabbages.push_back(pii);
        }     
        for(int i=0;i<cabbage_num;i++){
            if(visited[i]==0){
                queue <pair<int,int> > q;
                q.push(cabbages[i]);
                visited[i]=1;
            
            while(!q.empty()){
                pair<int,int> root = q.front();
                //cout << "root is " << root.first << " " << root.second << endl;
                q.pop();
                for(int j=0;j<cabbage_num;j++){
                    int count = 0;
                    if(visited[j]==0){
                        if(abs(cabbages[j].first-root.first)==1 && (cabbages[j].second - root.second)==0){
                           count ++; 
                        }
                        if(abs(cabbages[j].second-root.second)==1 && (cabbages[j].first - root.first)==0){
                            count ++;
                        }
                       if(count==1){
                           q.push(cabbages[j]);
                           visited[j] = 1;
                       } 
                    }
                }
            }
            worms++;
        }
        }
        answer.push_back(worms);
        }
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << "\n";
    }
}