JArchive 프로그래밍 일기

문제

유기농 배추 백준 1012

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 1012 유기농 배추
int t, n, m, k, x, y;
int ground[52][52];
int vis[52][52];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m );
}

void initground(){
  for(int i = 0; i < 52; i++) fill(ground[i], ground[i]+n, 0);
}

void initvis(){
  for(int i = 0; i < 52; i++) fill(vis[i], vis[i]+n, 0);
}

void bfs(int si, int sj){

  queue<pair<int,int>> qu;
  ground[si][sj] = 0;
  qu.push({si, sj});

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();

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

      if(!checkrange(nx, ny) || !ground[nx][ny]) continue;
      ground[nx][ny] = 0; // 방문 표시
      qu.push({nx, ny});
    }
  }

}

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

  cin >> t;

  while(t--){
    initground(); initvis();
    int answer = 0;

    cin >> m >> n >> k; // 가로길이, 세로길이, 배추개수

    while(k--){
      cin >> x >> y;  // 가로(열), 세로(행)
      ground[y][x] = 1;
    }

    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        if(ground[i][j] == 1){
          bfs(i, j);
          answer++;
        }
      }
    }
    cout << answer << '\n';
  }
  return 0;
}

리뷰

기본적인 bfs 문제였다.
2중 반복문에서 배추밭 1을 만나면, 인접한 배추밭을 모두 0으로 만든다.
bfs를 한 번 돌릴 때마다 배추밭 덩어리 개수를 셀 수 있으니까 answer를 1개씩 증가시킨다.