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

1012번: 유기농 배추

 

문제

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

 

 

풀이

잘 알려진 bfs 문제. M×N 배열을 모두 돌면서 값이 1인 동시에 아직 방문하지 않은 점들에 대해 bfs를 시행한다. bfs에선 해당 좌표를 방문처리한 후 상하좌우를 하나씩 체크하며 값이 1인 동시에 아직 방문하지 않았다면 큐에 추가해 준다. 위 방법을 큐가 빌 때까지 반복한다.

 

bfs를 한 번 진행하면 인접해있는 모든 배추는 방문하게 되므로, bfs를 진행한 횟수가 정답이 된다.

 

추가로 각 테스트케이스마다 visited 배열을 초기화해준다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int m, n;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
vector<vector<int>> v(50, vector<int>(50, 0));
vector<vector<bool>> visited(50, vector<bool>(50, false));

void bfs(int xx, int yy) {
  queue<pair<int, int>> q;
  q.push({xx, yy});
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny] && v[nx][ny] == 1) {
        visited[nx][ny] = true;
        q.push({nx, ny});
      }
    }
  }
}

void init() {
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
      v[i][j] = 0;
      visited[i][j] = false;
    }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int k, cnt = 0;
    cin >> m >> n >> k;
    init();
    while (k--) {
      int x, y;
      cin >> x >> y;
      v[x][y] = 1;
    }
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (v[i][j] == 1 && !visited[i][j]) {
          bfs(i, j);
          cnt++;
        }
    cout << cnt << '\n';
  }
  return 0;
}