BOJ - 1245 - 농장 관리

문제

1245번: 농장 관리

문제

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

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

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

입력

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

출력

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

구현

#include <iostream>

using namespace std;

// map
int n, m;
int map[104][104];
bool visited[104][104];

// joy
int dy[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
// ans
int ans = 0;
bool peak;
void dfs(int y, int x)
{
    visited[y][x] = 1;
    for(int i=0; i < 8; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m)
            continue;
        if(map[ny][nx] > map[y][x])
            peak = 0;
        if(map[ny][nx] == map[y][x] && !visited[ny][nx])
            dfs(ny, nx);
        
    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            cin >> map[i][j];

    for(int i=0; i < n; i++)
        for(int j=0; j < m; j++)
            if(!visited[i][j] && map[i][j])
            {
                peak = 1;
                dfs(i, j);
                if(peak)
                    ans++;
            }

    cout << ans << endl;
    return 0;
}

SOL

// 봉우리가 아닐 경우 
if(map[ny][nx] > map[y][x])
    peak = 0;
// 같은 높이고, 방문하지 않았을 경우 
if(map[ny][nx] == map[y][x] && !visited[ny][nx])
    dfs(ny, nx);

Reference & 다른 PS 모음집

GitHub - ggh-png/PS: 2021.01.11 start

DFS 깊이 우선 탐색