Gidhub BE Developer

[BOJ] 1012. 유기농 배추

2018-10-01
goodGid

Problem

Problem URL : 유기농 배추


[1] Answer Code (18. 10. 01)

#include<iostream>
#include<cstring>
using namespace std;

int map[50][50] = {0,};
int v[50][50];
int n,m;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void dfs(int x, int y){
    v[x][y] = 1;
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            if(!v[nx][ny] && map[nx][ny])
                dfs(nx,ny);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int tc;
    cin >> tc;
    
    while (tc--) {
        memset(map,0,sizeof(map));
        memset(v,0,sizeof(v));
        int k;
        cin >> n >> m >> k;
    
        for(int i=0; i<k; i++){
            int a,b;
            cin >> a >> b;
            map[a][b] = 1;
        }
        
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 1 && !v[i][j]){
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

Review

  • DFS.

Comments

Content