1012: 유기농 배추

문제

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

접근 방법 + 알고리즘

• 일단 완전탐색 + DFS 활용!
• 문제에서 주어진 배열을 2차원 배열이라고 하고
  배추벌래가 있는 곳을 cabbage_bug라고 표시하고
  탐색한 부분을 marked라고 표시한다.
• 메인 함수에서 일단 2차원 배열을 순회한다.
  • 단, 특정 원소가 이미 marked 상태인 경우 무시[continue]
  • 특정 원소가 cabbage_bug인 경우
    • 전체 카운터[문제에서 요구하는 값] 증가시키고
    • DFS(벡터, 위치-x, 위치-y) 시작

DFS(벡터, 위치-x, 위치-y)

• 핵심 내용
  • 지뢰찾기처럼 한 부분을 클릭하면 인접한 부분을 확장시키는 함수
• 위치-x와 위치-y를 기준으로 문제에서 요구하는 조건 그대로,
  • 상-하-좌-우에 cabbage_bug인 경우 && 상-하-좌-우가 marked가 아닌 경우
    • dfs(벡터, 상-하-좌-우 좌표값) 재귀함수 진행

코드

#include <iostream>
#include <vector>

#define CABBAGE_BUG 1
#define MARKED -10

using namespace std;

void dfs(vector<vector<int>>& array, int loc_x, int loc_y) {
    // Top
    if (loc_y-1 >= 0) {
        if (array[loc_y-1][loc_x] == CABBAGE_BUG) {
            array[loc_y-1][loc_x] = MARKED;
            dfs(array, loc_x, loc_y-1);
        }
    }

    // Down
    if (loc_y+1 < array.size()) {
        if (array[loc_y+1][loc_x] == CABBAGE_BUG) {
            array[loc_y+1][loc_x] = MARKED;
            dfs(array, loc_x, loc_y+1);
        }
    }

    // Left
    if (loc_x-1 >= 0) {
        if (array[loc_y][loc_x-1] == CABBAGE_BUG) {
            array[loc_y][loc_x-1] = MARKED;
            dfs(array, loc_x-1, loc_y);
        }
    }

    // Right
    if (loc_x+1 < array[loc_y].size()) {
        if (array[loc_y][loc_x+1] == CABBAGE_BUG) {
            array[loc_y][loc_x+1] = MARKED;
            dfs(array, loc_x+1, loc_y);
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin >> tc;

    for (int i = 0; i < tc; i++) {
        int counter = 0;
        int x, y, cabbage_count;
        cin >> x >> y >> cabbage_count;
        vector<vector<int>> array(y, vector<int>(x, 0));

        for (int cab_ctr = 0; cab_ctr < cabbage_count; cab_ctr++) {
            int cab_x, cab_y;
            cin >> cab_x >> cab_y;

            array[cab_y][cab_x] = CABBAGE_BUG;
        }

        for (int forall_vector = 0; forall_vector < y; forall_vector++) {
            for (int forall_vector_x = 0; forall_vector_x < x; forall_vector_x++) {
                if (array[forall_vector][forall_vector_x] == CABBAGE_BUG) {
                    counter++;
                    // Do the dfs
                    array[forall_vector][forall_vector_x] = MARKED;
                    dfs(array, forall_vector_x, forall_vector);
                }
            }
        }
        cout << counter << endl;
    }
    return 0;
}