[C++] 백준 온라인 저지 1012번 유기농 배추 풀이

배추밭에 필요한 배추흰지렁이의 최소 갯수를 구하는 문제

 

---

문제의 조건

 

1. 배추를 해충으로부터 보호하기 위해 배추밭에 배추흰지렁이를 놓을 것이다. 

 

2. 지렁이는 상하좌우에 인접한 배추에게 이동할 수 있다. 

 

3. 배추는 한 번에 많이 몰려있지 않고 밭 전체에 퍼져서 심어져 있다. 

아파트 단지처럼 배추도 단지별로 심어져 있음 

 

4. 필요한 지렁이의 최소 갯수 구해서 출력하기 

 

5. 테스트 케이스가 여러 개 주어질 수 있다. 

 

---

풀이 과정

 

1. BFS로 배추밭을 탐색하는데 전체 밭을 탐색해야 하기 때문에 2중 for문으로 [0, 0]번째부터 탐색한다. 

 

2. 배추 한 칸을 대상으로 상하좌우에 또 배추가 있는지 검사해서 연결된 배추가 있으면 다음에 방문할 큐에 추가

 

3. 하나의 배추 단지 검사가 끝나고 나면 정답 카운트를 증가시킨다. 

 

4. 하나의 테스트 케이스가 끝나면 정답 카운트를 출력한다. 

 

5. 다음 테스트 케이스 입력을 받아서 반복한다. 

 

---

 

 

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

using namespace std;

int main(int argc, const char * argv[])
{
    //상하좌우에 인접한 배추들을 탐색할 방향값 저장 
    vector<pair<int, int>> dir{
        make_pair(1, 0),
        make_pair(-1, 0),
        make_pair(0, 1),
        make_pair(0, -1)
    };
    
    int T;
    cin >> T;
    
    for (int i = 0; T > i; i++)
    {
        int M, N, K;
        cin >> M >> N >> K;
        //배추밭 2차원 배열
        vector<vector<bool>> flat(N, vector<bool>(M, false));
        for (int j = 0; K > j; j++)
        {
            int a, b;
            cin >> a >> b;
            flat[b][a] = true;
        }
        
        //방문 표시용 2차원 배열 
        vector<vector<bool>> visited(N, vector<bool>(M, false));
        int answer = 0;
        for (int j = 0; N > j; j++)
        {
            for (int k = 0; M > k; k++)
            {
                //0,0 부터 탐색하다가 배추를 만나면 입장 후 bfs 시작 
                if (!visited[j][k] && flat[j][k])
                {
                    queue<pair<int, int>> q;
                    q.emplace(make_pair(j, k));
                    
                    while (!q.empty())
                    {
                        auto curTile = q.front();
                        q.pop();
                        
                        visited[curTile.first][curTile.second] = true;
                        
                        for (int j = 0; dir.size() > j; j++)
                        {
                            auto next = make_pair(curTile.first + dir[j].first, curTile.second + dir[j].second);
                            if (0 > next.first || N <= next.first || 0 > next.second || M <= next.second) continue;
                            if (!visited[next.first][next.second] && flat[next.first][next.second])
                            {
                                q.emplace(next);
                                visited[next.first][next.second] = true;
                            }
                        }
                    }
                    
                    //여기로 오면 하나의 배추 단지 탐색이 끝난 것이다. 
                    //정답 카운트 증가 
                    answer++;
                }
            }
        }
        
        //여기로 오면 하나의 테스트 케이스가 끝난 것이다. 
        //정답 카운트 출력 
        cout << answer << endl;
    }
    
    return 0;
}