[백준/C++] 1245 농장 관리

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

코드

#include <iostream>
#include <queue>
using namespace std;

#define MAX 101
#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef pair<int, int> pi;
int arr[MAX][MAX];      
bool visit[MAX][MAX];   
int dx[8] = { 1, -1, 0, 0, 1, 1, -1, -1 }; 
int dy[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int n, m, ans; 

void bfs(int x, int y) {
    queue<pi> q;
    q.push({ x, y });
    visit[x][y] = true;

    bool top = true; 
    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++) {
            int gx = nx + dx[i];
            int gy = ny + dy[i];

            if (gx >= 0 && gx < n && gy >= 0 && gy < m) {
                if (arr[nx][ny] < arr[gx][gy]) top = false;
                if (!visit[gx][gy] && arr[nx][ny] == arr[gx][gy]) {
                    visit[gx][gy] = true;
                    q.push({ gx, gy });
                }
            }
        }
    }
    if (top) ans++;
}

int main() {
    FASTIO;
 
    cin >> n >> m;

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

    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (!visit[i][j])   
                bfs(i, j);
  
    cout << ans;
    return 0;
}

설명

BFS를 구현하면 되는데, 이때 for문 내에서 산봉우리를 확인합니다. 인접한 격자는 모두 산봉우리의 높이보다 작아야 하기 때문에 산봉우리 높이보다 높은 구간이 있을 경우 산봉우리 여부를 false로 표시합니다. 같은 높이를 가지는, 방문하지 않은 격자에 대해서는 큐에 넣어주며 탐색을 진행합니다. 

 

산봉우리일 경우에 ans를 1씩 더해주면서 산봉우리의 개수를 구합니다.

 

 

느낀 점

처음에 산봉우리 파트 구현에서 실수가 있었어서 한 번 틀렸습니다. 해당 부분을 수정해서 제출하니 바로 맞았습니다!