[ 백준 ] 1012번 - 유기농 배추 (C++)

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

1012번: 유기농 배추

 

 

[ 문제풀이 ]

 

1. 입력받은 좌표를 1로 바꾸어 배추의 위치를 기록합니다.

 

2. bfs를 통해 배추가 있는 곳을 0으로 갱신해주면서 연결되어 있는 배추들의 개수를 cnt에 저장합니다.

 

3. cnt를 출력합니다.

 

[ 소스코드 ]

 

#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
int N, M, K;
 
int arr[50][50];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs(int y, int x)
{
    queue<pair<int, int>> q;
    q.push({ y,x });
    arr[y][x] = 0;
 
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == 1) {
                    arr[yy][xx] = 0;
                    q.push({ yy,xx });
                }
            }
        }
    }
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d %d %d", &M, &N, &K);
        memset(arr, 0, sizeof(arr));
        
        for (int i = 0; i < K; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
 
            arr[y][x] = 1;
        }
 
        int cnt = 0;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
 
        printf("%d\n", cnt);
    }
}