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

문제

링크&사진

백준 1012

 

문제 내용

1이 배추가 심어진 곳, 0이 그렇지 않은 곳이다. 

지렁이가 있으면 배추를 해충으로부터 보호할 수 있는데, 인접한 배추들끼리는 지렁이 하나로도 충분하다.

배추가 심어져 있는 위치를 입력받아, 지렁이가 최소 몇 마리나 필요한지를 출력하면 된다.

 

 

문제 풀이

이 문제는 bfs, dfs 둘 모두로 풀 수 있는 문제이다.

 

코드

BFS 풀이

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};
int m, n, k;

void bfs(vector<vector<bool>> &arr, vector<vector<bool>> &visited, int r, int c) {
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;

    while (!q.empty()) {
        pair<int, int> point = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = dr[i] + point.first;
            int nc = dc[i] + point.second;

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && arr[nr][nc] && !visited[nr][nc]) {
                q.push({nr, nc});
                visited[nr][nc] = true;
            }
        }
    }
}

int solution() {
    cin >> m >> n >> k; // 열, 행, 배추 개수

    vector<vector<bool>> arr(n, vector<bool>(m, false));
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<pair<int, int>> baechu;

    int r, c;
    for (int i = 0; i < k; i++) {
        cin >> c >> r;
        baechu.push_back({r, c});
        arr[r][c] = true;
    }

    int cnt = 0;
    for (int i = 0; i < k; i++) {
        int r = baechu[i].first;
        int c = baechu[i].second;

        if (!visited[r][c]) {
            cnt++;
            bfs(arr, visited, r, c);
        }
    }
    return cnt;
}

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

    int T;
    cin >> T;

    while (T--) {
        cout << solution() << '\n';
    }
}

 

DFS 풀이

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int m, n, k;
bool arr[50][50];
bool visited[50][50];

void dfs(int r, int c) {
    visited[r][c] = true;

    for (int i = 0; i < 4; i++) {
        int nr = dr[i] + r;
        int nc = dc[i] + c;

        if (nr >= 0 && nr < n && nc >= 0 && nc < m && arr[nr][nc] && !visited[nr][nc]) {
            dfs(nr, nc);
        }
    }
}

int solution() {
    cin >> m >> n >> k; // 열, 행, 배추 개수

    vector<pair<int, int>> baechu;
    int r, c;
    for (int i = 0; i < k; i++) {
        cin >> c >> r;
        baechu.push_back({r, c});
        arr[r][c] = true;
    }

    int cnt = 0;
    for (int i = 0; i < k; i++) {
        int r = baechu[i].first;
        int c = baechu[i].second;
        if (!visited[r][c]) {
            cnt++;
            dfs(r, c);
        }
    }
    return cnt;
}

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

    int T;
    cin >> T;

    while (T--) {
        cout << solution() << '\n';
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 50; j++) {
                arr[i][j] = false;
                visited[i][j] = false;
            }
        }
    }
}

 

문제 코드 설명

dfs 풀이의 경우 재귀를 통해 문제를 풀었기 때문에, 넘겨주는 인자를 줄이려고 arr, visited 등의 배열을 전역 변수로 선언했다. 그렇기 때문에 테스트케이스마다 arr, visited 배열을 초기화시켜주는 작업이 필요하다.