[백준] 1012번 : 유기농 배추

문제

 

---

풀이

 

myunji.tistory.com/280

[백준] 2667번 : 단지번호붙이기

이 문제와 풀이가 동일하다.

오히려 이 문제는 연결된 배추의 그룹(?)수만 세면 되는거라 더 쉬운 셈이다.

---

소스코드

 

#include <iostream>
#include <cstring>
#include <utility>

using namespace std;

//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[52][52], M, N;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1,  0},  //하
                         {0,  -1}, //좌
                         {0,  1}}; //우

void dfs(pair<int, int> pos) { //인접한 모든 배추를 찾는 dfs
    for (int i = 0; i < 4; i++) { //현위치의 상하좌우 좌표를 row, col에 저장
        int row = pos.first + dir[i].first;
        int col = pos.second + dir[i].second;
        if (matrix[row][col] == 1) { //확인한 적 없는 배추(leaf)
            matrix[row][col] = 0; //방문 체크
            pair<int, int> next_pos = {row, col};
            dfs(next_pos); //재귀 호출
        }
    }
}

int findBug() {
    int cnt = 0; //총 벌레수

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (matrix[i][j] == 1) { //확인한 적 없는 배추(root)
                cnt++; //총 벌레 수 증가
                matrix[i][j] = 0;
                pair<int, int> start = {i, j};
                dfs(start); //인접한 모든 배추를 찾음
            }
        }
    }
    return cnt;
}

int main() {
    int T, K, row, col;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> M >> N >> K;
        for (int j = 0; j < K; j++) {
            cin >> col >> row;
            matrix[row + 1][col + 1] = 1;
        }
        cout << findBug() << '\n'; //총 벌레수 출력
        for (int i = 0; i < 52; i++) //2차원 배열 초기화
            memset(matrix[i], 0, sizeof(int) * 52);
    }
}

그냥 입력 받는 방법의 차이를 제외하곤 2667번과 굉장히 유사해서 할 말이 없다.

이 문제에서 더 추가된게 있다면 그걸 설명할텐데 오히려 2667번에서 뭐가 빠진거라 설명은 생략하도록 하겠다.