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

문제 링크입니다. https://www.acmicpc.net/problem/1245

1245번: 농장 관리

산봉우리의 갯수를 구하는 문제입니다.

여기서 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격좌들의 집합이라고 정의합니다.

산봉우리와 인접한 격좌는 모두 산봉우리의 높이보다 작아야한다고 합니다.

 

예시를 통해 산봉우리를 확인해본다면

해당 그림과 같이 3개가 됩니다.

따라서, 1이상의 같은 격좌로 이루어져 있으며, 8방향으로 이어지고, 주변보다 높이가 큰 좌표라고 할 수 있습니다.

 

산봉우리가 몇개인지 알기 위해서는

1. 1 이상의 좌표 값을 가진 좌표를 탐색한다.

2. 주변에 자신보다 큰 값의 좌표가 있는지 확인한다.

   2-1. 주변에 자신보다 큰 값이 있다면, 자신은 산봉우리가 아니라는 뜻이 됩니다.

3. 자신과 같은 값이 더 이상 나오지 않는다면 탐색을 종료합니다.(탐색은 8뱡향 탐색입니다.)

4. 자신이 산봉우리인지 확인했음으로 해당 결과에 따라 산봉우리의 갯수를 변경합니다.

 

이와 같은 접근방법을 사용한다면 쉽게 문제를 풀 수 있습니다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define INF 987654321
#define F first
#define S second

using namespace std;

int N, M;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
int check[101][71];
int map[101][71];
bool flag = true;

void bfs(int X, int Y){
    queue<pair<int, int>> q;
    q.push({X,Y});
    check[X][Y] = 1;
    while(!q.empty()){
        int x = q.front().F;
        int y = q.front().S;
        q.pop();
        for(int i = 0; i < 8; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
                if(map[xx][yy] > map[X][Y]) flag = false;
                if(check[xx][yy] != 0) continue;
                if(map[xx][yy] != map[X][Y]) continue;
                q.push({xx,yy});
                check[xx][yy] = 1;
            }
        }
    }
}

void solve(){
    int island = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(check[i][j] == 0 && map[i][j] != 0){
                bfs(i, j);
                if(flag) island++;
                flag = true;
            }
        }
    }
    cout << island;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.