1012 - 유기농 배추

• 난이도: 실버 2
• 날짜: 2023년 2월 16일
• 상태: Correct/Retry
• 추가 검토 여부: No
• 알고리즘 : DFS

solution

• pair array를 사용하여 배추가 심어져 있는지의 여부(0, 1)와 벌레가 도달 가능/불가능 여부(true, false)의 정보를 저장했다.
• 배열은 N*M의 크기를 가지는 일차원 배열이며 x, y값이 곧 행과 열의 index이므로 이를 이용하여 배열을 참조했다.
• dfs함수를 구현하여 기존의 벌레 도달 지역이 아닌 곳의 배추가 심어져 있다면 ans를 증가시켜 총 필요한 벌레의 수를 구했다.

code

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

void dfs(pair<int, bool> arr[], int N, int M, int i)
{
    arr[i].second = true;
    if(i%M != 0)
        if(arr[i-1].first == 1 && !arr[i-1].second)
            dfs(arr, N, M, i-1);
    if(i%M != M-1)
        if(arr[i+1].first == 1 && !arr[i+1].second)
            dfs(arr, N, M, i+1);
    if(i-M >= 0)
        if(arr[i-M].first == 1 && !arr[i-M].second)
            dfs(arr, N, M, i-M);
    if(i+M < N*M)
        if(arr[i+M].first == 1 && !arr[i+M].second)
            dfs(arr, N, M, i+M); 
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int testC;
    cin >> testC;
    int N, M, K;
    int x, y;
    int ans = 0;
    for(int c = 0; c < testC; c++)
    {
        cin >> M >> N >> K;
        pair<int, bool> * arr = new pair<int, bool>[N*M];
        ans = 0;
        for(int i = 0; i < N*M; i++)
        {
            arr[i].first = 0;
            arr[i].second = false;
        }
        for(int i = 0; i < K; i++)
        {
            cin >> x >> y;
            arr[M*y+x].first = 1;
        }
        for(int i = 0; i < N*M; i++)
        {
            if(arr[i].first == 1)
                if(!arr[i].second)
                {
                    dfs(arr, N, M, i);
                    ans++;
                }
        }
        cout << ans << endl;
    }
    return 0;
}

ref

1012번: 유기농 배추