[그래프 / BOJ 1012 / C++] 유기농 배추

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

1012번: 유기농 배추

1) 배열 전체를 탐색한다. 만약 방문표시(1)가 있거나 양배추가 안심어져있으면(0) 지나간다.
2) 만약 방문을 안했고, 양배추가 심어져있다면, count를 하고, dfs나 bfs를 시행하며 방문표시를 한다.
3) count를 출력한다.

전형적인 연결된 컴포넌트 문제이다.

배열 전체를 순회하며 dfs나 bfs를 시행하며 cnt를 해주면 된다.

 

이런 최단거리를 구하는 문제가 아니라면 코드가 더 짧은 dfs를 이용한다.

 

#include <bits/stdc++.h>

using namespace std;

int T, N, M, K, a, b;

int board[51][51];
int vis[51][51];

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

void dfs(int y, int x){
    vis[y][x] = 1;
    for(int dir = 0 ; dir < 4 ; dir++){
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        if(ny>=N || ny < 0 || nx>=M || nx < 0) continue;
        if(vis[ny][nx] || !board[ny][nx]) continue;
        
        dfs(ny,nx);
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    
    while(T--){
    cin >> M >> N >> K;
    int cnt = 0;
    for(int i = 0; i < 51; i++){
        fill(vis[i], vis[i]+51, 0);
        fill(board[i], board[i]+51, 0);
    }
    while(K--){
        cin >> b >> a;
        board[a][b] = 1;
    }
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            if(board[i][j] && !vis[i][j]){
               cnt++; dfs(i, j);
            }
        }
    }
    
    cout << cnt << '\n';
    }
    
}