BOJ 1012 ) 유기농 배추

 

1012번: 유기농 배추

DFS로 간단히 해결 할 수 있는 문제. 왠진 모르지만 예전에 풀려고 시도했다가 실패한 흔적이 남아있었다. 벡터를 이용해 밭의 크기를 런타임에 지정해주고 배추는 1로 표시한다. 방문여부는 배추가 없는 곳은 방문할 필요가 없으므로 기본은 모두 0으로, 배추가 있는 곳은 배추 위치를 표시하면서 같이 방문여부를 1로 변경해준다. 그 이후에는 반복문을 돌면서 배추가 심겨진 곳을 dfs로 탐색한다. 다음 칸을 방문할지 말지는 배추가 있는지와 방문한적이 없는지를 모두 고려해준다. 

#include <iostream>
#include <vector>
#define pii pair<int,int>
#define y first
#define x second
using namespace std;
int T, M, N, K, x, y;
pii dir[4]={{1,0},{0,1},{-1,0},{0,-1}};
vector<vector<int>> adj;
vector<vector<bool>> visited;

void dfs(int dx, int dy){
    visited[dx][dy]=false;
    for(int i=0;i<4;i++){
        int nextx=dx+dir[i].x;
        int nexty=dy+dir[i].y;
        if(nextx<0||nextx>=N||nexty<0||nexty>=M)continue;
        if(adj[nextx][nexty]==1 && visited[nextx][nexty]==true) 
            dfs(nextx,nexty);
    }
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>M>>N>>K;
        adj=vector<vector<int>> (N+1, vector<int>(M+1));
        visited=vector<vector<bool>> (N+1, vector<bool>(M+1));
        
        while(K--){
            cin>>x>>y;
            adj[y][x]=1;
            visited[y][x]=true;
        }    
        int res=0;
        
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(visited[i][j]==false)continue;
                res++;
                dfs(i,j);
            }
        }
        cout<<res<<'\n';   
    }
}