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

바로 지난번에 풀었던 문제가 DFS와 BFS 문제였는데, 이번에 바로 BFS개념을 활용할 수 있는 문제를 골라보았다.

 

실버2 난이도

---

1. 문제 해결방법 구상

위의 문제 설명을 풀어보면, 결국은 1로 이루어진 덩어리의 개수가 몇 개인지 파악하는 문제이다. 덩어리에는 배추가 하나가 있을 수도, 두 개, 혹은 여러 개가 있을 수도 있다.  

덩어리를 파악하기 위해서는 BFS를 사용하는 것이 가장 효율적이므로 BFS를 선택했다.

배추밭의 첫 모퉁이부터 끝 모퉁이까지 훑어가면서 BFS를 시행할 수 있는 조건이면 BFS를 시행하고 아닌 경우 넘어간다.  

 

BFS를 시행할 수 있는 조건이라면

(1) 해당 배추밭 영역을 방문하지도 않았어야 하고

(2) 해당 영역에 배추가 있어야 한다. (배추가 없으면 덩어리를 파악할 이유도 없으므로)  

---

2. 해결 방법 구상에 따라 구현

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

int T, M, N, K, X, Y, cnt;
bool field[50][50];
bool visited[50][50];

// 상하좌우 순서대로
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void BFS(int row, int col) {
    queue<pii> q;

    q.push({row, col});
    visited[row][col] = true;

    while(!q.empty()) {
        pii f = q.front();
        for(int i = 0; i < 4; i++) {
            int nr = f.first + dr[i];
            int nc = f.second + dc[i];
            // 배추밭의 영역에 벗어나는 경우는 생각해주면 안됨
            if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
            // 조건 (1)과 (2)의 경우. 방문하지 않았거나, 배추가 없거나
            if(visited[nr][nc] || !field[nr][nc]) continue;
            q.push({nr, nc});
            visited[nr][nc] = true;
        }
        q.pop();
    }

    cnt++;
}

void solve() {
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < N; j++) {
            // (0, 0) 부터 (M-1, N-1)까지 다 탐색
            if(field[i][j] && !visited[i][j]) BFS(i, j);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    for(int i = 0; i < T; i++) {
        cnt = 0;
        cin >> M >> N >> K;
        memset(field, 0, sizeof(field));
        memset(visited, 0, sizeof(visited));
        for(int j = 0; j < K; j++) {
            cin >> X >> Y;
            field[X][Y] = true;
        }
        solve();
        cout << cnt << endl;
    }

}

---

3. 느낀 점

 

그냥 전형적인 BFS 문제였다.

차근차근 정복해나가자.

 

//문제제기 및 피드백 언제든지 감사히 받겠습니다.​