[c++/알고리즘] 백준 1012 유기농배추 : dfs

문제 풀이

• 출발점이 따로 존재하지 않아서 BFS보다 DFS가 더 적합하다고 생각하여 DFS로 접근하였다. -> 다른 블로그보니 BFS로 푼 경우가 꽤 된다.
• 한칸에 지렁이가 살고 있으면 왼/오/위/아래로 인접한 다른 배추로 이동할 수 있어 지렁이가 필요없다.
• 배추의 위치는 x : 0<=x<M ,y : 0<=y<N 이 주어진다.
• 
• 배추가 인접해 있는 곳을 한개씩 카운트한다.

나의 코드

#include <iostream>
#include <cstring>
using namespace std;
int chk[51][51];
int map[51][51];
int dx[4] = {0, 1, 0 ,-1};
int dy[4] = {1, 0, -1, 0};

void DFS(int x, int y){

    for(int i=0; i<4; i++) {
        if (chk[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 1) {
            chk[x+dx[i]][y+dy[i]] = 1;
            DFS(x+dx[i], y+dy[i]);
        }
    }
}

int main(){
    int t, m, n, k, a, b, cnt = 0;

    cin >> t;

    for(int i=0; i<t; i++){
        cin >> m >> n >> k;
        // 배추의 갯수만큼 해당 x,y좌표에 배추 입력받기
        for(int j=0; j<k; j++){
            cin >> a >> b;
            map[a][b] = 1;
        }
        if(k == 1){
            cout << 1 << endl;
            continue;
        }
		
        // 아직 방문하지 않았고, 배추가 심어져 있는곳에서 DFS 시작
        // DFS가 종료되면 ( 한 지점에서 인접한 지점을 모두 방문했을때)
        // cnt(배추지렁이의 수)를 1씩 증가시킨다.
        for(int x=0; x<n; x++){
            for(int y=0; y<m; y++){
                if(chk[y][x] == 0 && map[y][x] == 1){
                    chk[y][x] = 1;
                    DFS(y, x);
                    cnt++;
                }
            }
        }

        cout << cnt << endl;
        cnt = 0;
        memset(chk, 0, sizeof(chk));
        memset(map, 0, sizeof(map));
    }

    return 0;
}