[BOJ] 1245번 - 농장 관리

1245번 - 농장관리

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	256	99	78	46.988%

문제

농부 민식이가 관리하는 농장은 N*M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 guard를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1<N≤100), M(1<M≤70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자들의 높이를 의미하는 M개의 정수가 입력된다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

예제 입력 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

예제 출력 1

3

출처

https://www.acmicpc.net/problem/1245

알고리즘 분류

• 그래프 이론
• 그래프 탐색

접근 방법

전형적인 DFS 문제이다. N*M의 크기가 크지 않으므로 충분히 방문되지 않은 모든 문제들에 대해 DFS를 돌려서 해결하면된다.

DFS내부에서 같은 높이의 봉우리에 해당하는 좌표로 이동하면서, 인접 노드에 자기 자신보다 큰 언덕(?)이 있는 지 확인만 해주면 된다.
이 과정은 이동가능한 모든 경로를 계산할 때 확인해주면된다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N,M;
int farm[101][71];
bool visited[101][71] = {false, };
bool isPeak = true;
const int dir[8][2] = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
void DFS(int y, int x){
    for(int i=0; i<8; i++){
        int ny = y + dir[i][0], nx = x + dir[i][1];
        if( ny < 0 || ny >= N || nx < 0 || nx >= M ) continue;

        // 인접 칸에 더 높은 봉우리가 있는가?
        if( farm[y][x] < farm[ny][nx] ) isPeak = false;

        // 해당하는 산봉우리들을 탐색
        if( visited[ny][nx] || farm[y][x] != farm[ny][nx] ) continue;
        visited[ny][nx] = true;
        DFS(ny,nx);
    }
    return ;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    int answer = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if( !visited[i][j] ){
                isPeak = true;
                DFS(i, j);
                if( isPeak ) answer += 1;
            }
        }
    }
    cout << answer ;
    return 0;
}