[BOJ] #1012 유기농 배추

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

1012번: 유기농 배추

---

그간 일본여행을 다녀오느라 블로그나 공부를 제대로 못했었는데 역시 오랜만에 하니까 기억이 잘 안난다. PS는 그 무엇보다 그냥 매일 꾸준히 하는것이 실력향상을 위한 가장 빠른길인듯 하다.

이 문제는 #2667 단지번호붙이기와 비슷한 유형의 문제다. 이전에 블로그에 올렸던 문제이기도 한데,

1. 가중치가 없는 그래프에서 최단 경로를 찾아야 한다거나
2. 그런 최단 경로의 갯수를 구한다거나
3. 어떤 행렬이나 지도를 주고 그 지도에서 같은 부분으로 묶이는 영역을 구한다거나

BFS로 가닥을 잡고 풀어야하는 문제의 유형들 중 3번 유형에 해당하는 문제이다. 다만 #2667 문제와 다른점은, 문제에서 주어지는 입출력 조건이 조금 다르다는 정도? BFS로 탐색하는것, 상하좌우를 이동하며 탐색해야 하는 것 같은 문제를 해결하기 위한 큰 틀에서는 같은 매커니즘을 공유하는 문제라 생각한다.

문제를 풀면서 생긴 조그마한 이슈가 있었는데, BFS 함수 내의 while문 조건에 !가 빠져있었다. 분명히 다 맞는 매커니즘인데 거의 30분동안 그것도 모르고 계속 헤메다 딱 발견하고서는 엄청난 현타... 저런 사소한 구문 하나가 빠지더라도 코드 전체는 완전히 달라지게 된다. 항상 오타에 주의하자...

#include <iostream>
#include <queue>

#define MAX 51

using namespace std;

queue<pair<int,int>> Q;
bool visited[MAX][MAX] = { false };
int arr[MAX][MAX] = { 0 };

int M, N, K;
int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };
            //상  하  좌  우 

void reset(int m, int n) {
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            visited[i][j] = false;
            arr[i][j] = 0;
        }
    }
}

void BFS(int x, int y) {
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX >= 0 && newX < M) && (newY >= 0 && newY < N)) {
                if (visited[newX][newY] == false && arr[newX][newY] == 1) {
                    Q.push(make_pair(newX, newY));
                    visited[newX][newY] = true;
                }
            }
        }
    }
}

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

    int T;
    cin >> T;

    while(T-->0) {
        reset(M,N);
        int cnt=0;
        cin >> M >> N >> K;

        for (int i=0; i<K; i++) {
            int a, b;
            cin >> a >> b;

            arr[a][b] = 1;
        }   //배추 입력

        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j] == false && arr[i][j] == 1) {
                    BFS(i,j);
                    cnt++;
                }
            }
        }

        cout << cnt << '\n';
    }

    return 0;
}