[백준 1012] 유기농 배추

🔗알고리즘 문제

처음으로 풀어본 DFS문제이다. 잘 풀어내긴 하였지만 아직 DFS를 사용해서 잘 푼 것인지 내가 발상을 잘 해낸 것인지에 대한 의문이 들어 더욱 많은 관련 문제를 풀어봐야겠다는 생각이 들었다.

문제 분석

이 문제는 간단히 말해서 0으로 가득 찬 세계에서 1로 이루어진 공간이 몇 군데 있는 가를 판단해내면 되는 문제이다.

* 이 때 1이 서로 붙어있으면 같은 공간으로 친다. (대각선은 제외한다.)

발상

1로 이루어져 있는 모든 공간을 체크하기 위해서 우선 for문을 돌며 2차원 배열에 1을 찾고, 만약 1을 찾았다면 해당 1과 붙어 있는 모든 1을 체크해주면 되겠다라고 생각했다.

알고리즘 설계

2차원 배열을 처음부터 돌고 1을 찾았다면 해당 1을 주변으로 상하좌우 내 방향의 배열을 재탐색 해주었다. 이 때 1을 찾는다면 재귀형식으로 함수를 진행시켜 붙어있는 모든 1을 찾을 수 있도록 하였다.

// 탐색 함수 내부
for(int y = -1; y <= 1; y++)
{
    for(int x = -1; x <= 1; x++)
    {
        if(x == 0 || y == 0)
        {
        	// _x, _y 주변 상하좌우를 탐색하기
            if(arr[_y + y][_x + x] == 1)
            {
                arr[_y + y][_x + x] = 2;
                // 탐색 성공 시 재귀식으로 진행
                check(arr, _x + x, _y + y);
            }
        }
    }
}

코드

#include<iostream>
#include<cstring>

using namespace std;

void check(int arr[50][50], int _x, int _y){
    for(int y = -1; y <= 1; y++){
        for(int x = -1; x <= 1; x++){
            if(x == 0 || y == 0){
                if(_x + x < 0 || _y + y < 0 || _x + x >= 50 || _y + y >= 50){
                    continue;
                }

                if(arr[_y + y][_x + x] == 1){
                    arr[_y + y][_x + x] = 2;
                    check(arr, _x + x, _y + y);
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int arr[50][50] = {};
    
    int t;
    int n;
    int m;
    int k;

    int answer = 0;

    cin >> t;

    while(t--){
        memset(arr, 0, sizeof(arr));
        answer = 0;

        cin >> n >> m >> k;

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

        for(int x = 0; x < n; x++){
            for(int y = 0; y < m; y++){
                if(arr[y][x] == 1){
                    arr[y][x] = 2;
                    ++answer;
                    check(arr, x, y);
                }
            }
        }

        cout << answer << "\n";
    }
}