[BOJ 1012] 유기농 배추

1. 문제

2. 구현 아이디어 - 맞았습니다!!

구역의 개수를 세면 되는 그래프 문제이다.

BFS와 DFS 둘 다 가능하기 때문에 편한대로 사용하면 된다. 나는 BFS로 문제를 풀었다.

 

주의 ⚠️
나는 평소에 행을 x, 열을 y로 푸는데 배추의 위치가 (열, 행) 순으로 들어오기 때문에 순서가 바뀌지 않도록 주의하여야 한다!

 

2중 반복문으로 배추밭 배열을 돌면서 현재 위치가 1이고 아직 방문하지 않았다면 해당 좌표를 시작점으로 BFS를 돈다.

BFS를 돈 뒤, 배추흰지렁이의 개수(ret)를 +1해준다.

 

일반적인 BFS 문제이고, 자세한 설명은 코드에 주석으로 달겠다.

 

#include <bits/stdc++.h>

using namespace std;

int t;
int m, n, k;
int x, y;
int arr[54][54]; // 배추밭
bool visited[54][54]; // 방문 여부
queue<pair<int, int>> q; // BFS에 사용할 큐
int ret; // 배추흰지렁이의 개수 (결과)
int cx, cy; // 현재 위치
int nx, ny; // 다음 위치

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
    cin >> t;

    for (int a = 0; a < t; ++a) {
        // 테스트 케이스마다 초기화
        ret = 0;
        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));

        // 가로, 세로, 배추의 위치
        cin >> m >> n >> k;

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

        // BFS
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 이미 방문했거나 배추가 심어져있지 않다면 skip
                if (visited[i][j] || arr[i][j] == 0) continue;

                q.push({i, j});
                while (!q.empty()) {
                    cx = q.front().first;
                    cy = q.front().second;
                    q.pop();

                    for (int l = 0; l < 4; ++l) {
                        nx = cx + dx[l];
                        ny = cy + dy[l];

                        // 좌표가 배열을 벗어나지 않았을 때
                        if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                            if (arr[nx][ny] == 1 && !visited[nx][ny]) {
                                q.push({nx, ny});
                                visited[nx][ny] = true;
                            }
                        }
                    }
                }
                // BFS를 돈 뒤 배추흰지렁이의 개수를 +1
                ret++;
            }
        }

        cout << ret << "\n";
    }
    return 0;
}