[BOJ] 1012_유기농 배추

유기농 배추

문제 링크: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

이문제 분류가 그래프, DFS 이길래 왜 그런 문제인지 처음에는 이해가 안갔다.

• 첫 코드

    #include<iostream>
    using namespace std;
  
    int check(bool arr[50][50], int x, int y) {
        for (int k = -1; k < 2; k++) {
            if ((y + k) < 0 || k == 0 || (y + k) >= 50)
                continue;
            if (arr[x][y + k] == 1)
                return 0;
        }
        for (int i = -1; i < 2; i++) {
            if ((x + i) < 0 || i == 0 || (x + i) >= 50)
                continue;
            if (arr[x + i][y])
                return 0;
        }
        return 1;
    }
    int main() {
        int n;
        cin >> n;
        while (n--) {
            int M, N, K;
            cin >> M >> N >> K;
            bool arr[50][50] = { 0, };
            int count = 0;
  
            while (K--) {
                int x, y;
                cin >> x >> y;
                count += check(arr, x, y);
                arr[x][y] = true;
            }
            cout << count << endl;
        }
        return 0;
    }

  • 애초에 받을 때부터 주변을 살피고 배추가 심어져 있으면 누적하지 않는 알고리즘을 구현했다.
  • 예제도 옳게 나오길래 이게 맞는 줄 알았다.
  • 하지만 다음과 같은 상황에서 답이 다르게 나옴을 후에 깨달았다.
  • 100 -> 101 이 순으로 심어져 있을 경우 이미 벌레의 수는 2이다.
  • 하지만 여기서 가운데에 심어질 경우 111은 벌레의 수가 1개로 세어져야 하나, 이미 앞에서 2개로 세었기 때문에 계속 답이 아니라고 나왔던 것이다.

그제서야 이게 DFS\BFS문제였음을 이해했다.
전체 맵에서 모든 배추의 좌표를 받고 그 후 이어져있는 1을 탐색해야함을 알았다.
나는 DFS를 선택했고, 재귀함수를 시작하는 코드를 구성했다.

• 정답코드

    #include<iostream>
    using namespace std;
  
    int x_[4] = { 1, -1, 0, 0 };
    int y_[4] = { 0, 0, 1, -1 };
    void check(bool arr[50][50], int x, int y) {
        for (int i = 0; i < 4; i++) {
            if (x + x_[i] < 0 || y + y_[i] < 0 || x + x_[i] >= 50 || y + y_[i] >= 50)
                continue;
            if (arr[x + x_[i]][y + y_[i]]) {
                arr[x + x_[i]][y + y_[i]] = false;
                check(arr, x + x_[i], y + y_[i]);
            }
        }
    }
    int main() {
        int n;
        cin >> n;
        while (n--) {
            int M, N, K;
            cin >> M >> N >> K;
            bool arr[50][50] = { 0, };
            int count = 0;
  
            while (K--) {
                int x, y;
                cin >> x >> y;
                arr[x][y] = true;
            }
            for (int k = 0; k < 50; k++) 
                for (int i = 0; i < 50; i++) 
                    if (arr[k][i]) {
                        check(arr, k, i);
                        count++;
                    }
            cout << count << endl;
        }
        return 0;
    }