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

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

1012번: 유기농 배추

<알고리즘 분류>

   - Graph Searching

   - DFS(Depth First Search)

 

<풀이> 

  1. 한마디로 말하자면, 배추밭이 몇 덩이(영역)있냐는 것이 문제다.    

  2. 바로 DFS를 떠올렸다. 

 배추가 있는 한 지역을 확인하면, 그 주변의 배추들을 다 찾을때까지 DFS한다. 

 위의 과정을 반복한다. 

 

<주의사항>

  1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북)에 대한 인덱스를 미리 받아야 한다. 이때, 주어진 N*M 배열을 넘어가선 안 된다.

  2. visited[51][51] 배열을 통해 이미 방문했는지 체크해야 한다. 안하면 중복 카운트가 될 수 있다. 

 

 

 

<코드>

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int T, M, N, K;
int area[51][51]= {0,};
bool visited[51][51] = {false,};
int dx[4] = {-1,0,1,0}; //시계방향 탐색
int dy[4] = {0,1,0,-1};
int cnt = 0;

void dfs(int y, int x){
    visited[y][x] = true;

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

        if (nx >=0 && nx < M && ny >= 0 && ny < N){
            if(area[ny][nx] == 1){   //배추가 있다면 
                if(!visited[ny][nx]){   //지나치지 않았다면 
                    dfs(ny, nx); 
                }
            }
        }

        else continue;
    }
}


int main(){
    cin >> T;
    while(T--){
        cin >> M >> N >> K;

        for (int i=0; i<K; i++){
            int x, y;
            cin >> x >> y;
            area[y][x] = 1;
        } 

        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                //cout << i << " " << j << " " <<  visited[i][j]<<"\n";
                if (area[i][j] == 1 && (!visited[i][j])){
                    cnt++; 
                    dfs(i, j);
                    
                }
            }
        }

        cout << cnt << "\n";

        cnt = 0;
        memset(area, 0, sizeof(area));
        memset(visited, false, sizeof(visited));

    }
}