[C++] BOJ (백준) 1012 : 유기농 배추

문제

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

코드 1 (DFS)

#include <iostream>
#include <vector>

#define CABBAGE 1

using namespace std;

int m, n, k;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<vector<int>> map;
vector<vector<int>> isProtected;
vector<pair<int, int>> cabbage;

void input() {
  cin >> m >> n >> k;
  map = vector<vector<int>>(m, vector<int>(n));
  isProtected = vector<vector<int>>(m, vector<int>(n));
  cabbage.resize(k);
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    map[x][y] = CABBAGE;
    cabbage[i] = {x, y};
  }
}

void protect(int x, int y) {
  isProtected[x][y] = true;
  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx == -1 || nx == m || ny == -1 || ny == n) continue;
    if (isProtected[nx][ny] || map[nx][ny] != CABBAGE) continue;
    protect(nx, ny);
  }
}

int solve() {
  int cnt = 0;
  for (auto [x, y]: cabbage) {
    if (!isProtected[x][y]) {
      protect(x, y);
      cnt++;
    }
  }
  return cnt;
}

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

  int t;
  cin >> t;
  while (t--) {
    input();
    cout << solve() << '\n';
  }
  return 0;
}

설명

배추의 위치를 저장한 벡터 cabbage를 순회하면서, 아직 보호되지 않은 배추를 발견하면 해당 배추와 인접한 모든 배추들을 보호하고(protect 함수), 사용한 지렁이의 수를 카운트한다. protect 함수는 DFS를 이용하여 구현하며, 재귀로 상하좌우 4방향 중 가능한 방향으로 뻗어나간다.

 

코드 2 (BFS)

#include <iostream>
#include <vector>
#include <queue>

#define CABBAGE 1

using namespace std;

int m, n, k;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<vector<int>> map;
vector<vector<int>> isProtected;
vector<pair<int, int>> cabbage;
queue<pair<int, int>> q;

void input() {
  cin >> m >> n >> k;
  map = vector<vector<int>>(m, vector<int>(n));
  isProtected = vector<vector<int>>(m, vector<int>(n));
  cabbage.resize(k);
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    map[x][y] = CABBAGE;
    cabbage[i] = {x, y};
  }
}

void protect(int x, int y) {
  isProtected[x][y] = true;
  q.emplace(x, y);
  while (!q.empty()) {
    auto [cx, cy] = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
      int nx = cx + dx[i];
      int ny = cy + dy[i];
      if (nx == -1 || nx == m || ny == -1 || ny == n) continue;
      if (isProtected[nx][ny] || map[nx][ny] != CABBAGE) continue;
      isProtected[nx][ny] = true;
      q.emplace(nx, ny);
    }
  }
}

int solve() {
  int cnt = 0;
  for (auto [x, y]: cabbage) {
    if (!isProtected[x][y]) {
      protect(x, y);
      cnt++;
    }
  }
  return cnt;
}

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

  int t;
  cin >> t;
  while (t--) {
    input();
    cout << solve() << '\n';
  }
  return 0;
}

설명

배추의 위치를 저장한 벡터 cabbage를 순회하면서, 아직 보호되지 않은 배추를 발견하면 해당 배추와 인접한 모든 배추들을 BFS를 이용해 보호하고 사용한 지렁이의 수를 카운트한다.