[백준] 1012 유기농 배추 - C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/1012

---

2. 풀이과정

• 문제 해결의 흐름

1.  문제를 살펴보면, 배추가 심어진 위치값들이 주어지고 서로 연결된 배추들이 하나의 집합(덩어리)를 형성함을 알 수 있습니다. 따라서 이 문제는 bfs를 통해 그래프에서 연결된 요소들의 개수를 찾아내는 문제임을 파악하였습니다.
2.  입력값을 저장하기 위해 배추 밭은 저장하는 2차원 벡터(graph), 방문 여부를 체크하는 2차원 벡터(visited)를 사용하였습니다. 그러나 테스트케이스마다 graph와 visited를 초기화해야 하므로 다음 2가지 방법 중 하나를 사용할 수 있었습니다.
   1. 전역 변수 2차원 벡터를 선언하고 assign()을 활용하여 크기를 재할당한다.
   2. 테스트케이스마다 새로운 지역 변수로 2차원 벡터를 생성한다.
3. 친구가 알려준 assign 메서드를 활용해볼 겸 1.의 방법으로 테스트케이스별 크기를 동적으로 재할당하는 방법을 사용하였습니다. 
4. 이후 모든 좌표값들을 탐색하며 아직 방문하지 않은, 즉 집합 형성이 되지 않은 배추에 대해 bfs를 수행합니다. 

#include <iostream>
#include <queue>

using namespace std;

int T, R, C, K, cnt;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
vector<vector<int> > graph(51, vector<int>(51,0));
vector<vector<int> > visited(51, vector<int>(51, 0));
queue<pair<int, int> > q;

void bfs(int r, int c) {
    q.push(make_pair(r,c));
    visited[r][c] = 1;
    cnt += 1;

    while (!q.empty()) {
        int current_r = q.front().first;
        int current_c = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int next_r = current_r + dr[i];
            int next_c = current_c + dc[i];

            if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;

            if (graph[next_r][next_c] == 1 && visited[next_r][next_c] == 0) {
                q.push(make_pair(next_r, next_c));
                visited[next_r][next_c] = 1;
            }
        }
    }

}

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

    // 0. 입력 받기
    cin >> T;

    for (int i = 0; i < T; ++i) {
        cin >> R >> C >> K;
        graph.assign(R, vector<int>(C, 0));
        visited.assign(R, vector<int>(C, 0));

        for (int i = 0; i < K; ++i) {
            int r, c;
            cin >> r >> c;
            graph[r][c] = 1;
        }

        // 1. bfs 수행
        cnt = 0;
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (graph[r][c] == 1 && visited[r][c] == 0) {
                    bfs(r,c);
                }
            }
        }

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

    return 0;
}

---

3. 후기

 친구에게 배운 전역 벡터를 사용하며 assing() 메서드를 직접적으로 활용하는 방법을 수 있어 뿌듯합니다 ㅎㅎ.