백준 1245 : 농장 관리(C++)

문제

풀이

이 문제는 그래프와 DFS를 이용해서 풀었습니다.
각 지점에서 인접한 지점은 총 8개입니다.(일반적으로)
기본 아이디어는 각 지점에서 DFS를 해서 DFS를 호출한 지점의 높이보다 큰 높이가 있는 지점이 없으면 산봉우리입니다.
(만약, 높이가 같은 지점이 있다면 DFS를 호출해줍니다.)

코드

#include <iostream>

#define endl "\n"
#define init ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int farm[100][70];
bool visited[100][70] = {false, };
bool flag = true;

int x[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int y[8] = {0, 1, -1, 1, -1, 0, 1, -1};

int N, M;

void DFS(int i, int j) {
    visited[i][j] = true;

    for(int k = 0; k < 8; k++) {
        int i_ = i + y[k];
        int j_ = j + x[k];

        if(i_ < 0 || j_ < 0 || i_ >= N || j_ >= M) {
            continue;
        }

        if(farm[i][j] < farm[i_][j_]) {
            flag = false;
        }

        if(visited[i_][j_] == true) {
            continue;
        }

        if (farm[i][j] != farm[i_][j_]) {
            continue;
        }

        if(farm[i][j] == farm[i_][j_]) {
            DFS(i_, j_);
        }
    }
}

int main() {
    init
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            int data;
            cin >> data;
            farm[i][j] = data;
        }
    }

    int sum = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0 ; j < M; j++) {
            if(visited[i][j] == false) {
                flag = true;
                DFS(i, j);
                if(flag == true) {
                    sum++;
                }
            }
        }
    }
    cout << sum << endl;
    return 0;
}