백준 1012번 [유기농 배추](C++) -yes6686- 티스토리

백준 문제 풀이: 1012 [유기농 배추]

---

문제 링크: https://www.acmicpc.net/problem/1012

문제 설명:

가로길이 M, 세로길이 N의 밭에 배추가 심어져 있습니다. 배추는 연결되어 있는 곳끼리 한 그룹으로 간주하며, 독립된 배추 그룹의 개수를 구하는 프로그램을 작성하세요.

입력 조건:

• 첫째 줄에 테스트 케이스의 개수 T가 주어집니다.
• 각 테스트 케이스의 첫 줄에는 M(가로길이), N(세로길이), K(배추가 심어진 위치의 개수)가 주어집니다.
• 이어지는 K줄에는 배추가 심어진 좌표 (x, y)가 주어집니다.

출력 조건:

• 각 테스트 케이스마다 필요한 최소의 배추흰지렁이 마리 수를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

queue<pair<int, int>> q;
int arr[51][51]; // 배추 위치
int visited[51][51]; // 방문 여부
int dx[4] = {1, -1, 0, 0}; // 상하좌우 이동
int dy[4] = {0, 0, 1, -1};
int n, m, k; // 세로, 가로, 배추 개수

void bfs(int x, int y) {
    q.push({x, y});
    while (!q.empty()) {
        int kx = q.front().first;
        int ky = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = kx + dx[i];
            int ny = ky + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (visited[nx][ny] || !arr[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

int main() {
    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        cin >> m >> n >> k;
        int cnt = 0; // 그룹 수
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));

        // 배추 위치 입력
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            arr[y][x] = 1;
        }

        // BFS 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && arr[i][j]) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }

        // 결과 출력
        cout << cnt << '\n';
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 BFS를 사용하여 배추 그룹을 찾아내고, 그룹의 개수를 세어 출력합니다.

• 입력 처리:
  • `arr[y][x]`를 사용하여 배추가 심어진 위치를 1로 표시합니다.
• BFS 탐색:
  • 배추가 있는 위치를 시작점으로 BFS를 수행하여 연결된 배추를 모두 방문 처리합니다.
  • 방문하지 않은 배추 그룹을 탐색할 때마다 `cnt`를 증가시킵니다.
• 초기화:
  • 테스트 케이스마다 `arr`와 `visited`를 초기화합니다.

시간 복잡도 분석:

• 배추 위치 입력: O(K).
• BFS 탐색: O(N × M).

전체 시간 복잡도는 O(T × (N × M + K))로 효율적으로 처리 가능합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

출력:
5
1

각 테스트 케이스에서 배추 그룹의 개수를 정확히 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!