[백준/c++] BOJ 1245 - 농장 관리

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

1245번: 농장 관리

 

문제 설명

NxM 크기의 농장이 있다. 산봉우리가 몇 개 있는지 세려고 한다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. ("인접하다"의 정의는 X좌표 차이와 Y좌표 차이가가 모두 1 이하일 경우로 정의된다.) 격자 내에 산봉우리의 개수가 총 몇 개인지 구한다.

N(1 < N <= 100) ,  M (1 < M <= 70)

해결

bfs의 로직은 다른 문제와 다르지 않다. 다만 대각선으로도 방문할 수 있으므로 반복문을 8번 돌아 주어야 한다.

문제는 봉우리를 어떻게 체크하냐인데, 모든 격자들을, 같은 숫자만 bfs를 돌려 주면 된다.

 

bfs를 돌았을 때, 주변에 더 높은 숫자가 있다면 ck를 0으로 바꾼다. 이는 현재 높이가 산 봉우리가 아니라는 뜻이다.

같은 숫자만 찾아 다니면서 점점 영역을 넓혔는데 더 큰 높이를 만나지 않은 경우, 그 부분은 산봉우리가 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int board[101][71];
int visited[101][71];
int n, m, ans = 0, ck = 1;
int dx[8] = { 1, -1, 0, 0, -1, -1, 1, 1 }, dy[8] = { 0, 0, 1, -1, -1, 1, -1, 1 };

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

void bfs(int i, int j) {
    queue<pair<int, int>> q;
    q.push({ i, j });
    visited[i][j] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 8; dir++) {
            int nx = dx[dir] + cur.x, ny = dy[dir] + cur.y;
            if (range_over(nx, ny)) continue;
            if (board[nx][ny] > board[cur.x][cur.y]) ck = 0;
            if (board[nx][ny] != board[cur.x][cur.y] || visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push({ nx, ny });
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j]) continue;
            ck = 1;
            bfs(i, j);
            if (ck) ans++;
        }
    }
    cout << ans;
}