[BOJ / C++] 1245번 : 농장 관리

문제

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

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

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

입력

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

출력

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

Solved.ac 레벨

골드 V

풀이

헷갈릴 부분이 있었던 그래프 탐색 문제.

 

먼저 문제에서 세어야 하는 산봉우리에 대한 정의가 헷갈려서 시행착오가 좀 있었다.

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

나는 높이가 4인 격자와 높이가 3인 격자는 같은 산봉우리로 취급할 수 없는 줄 알았다. 하지만 인접한 격자들과 차이가 1이라면 한 개의 산봉우리로 셀 수 있다. X좌표와 Y 좌표 차이 모두 1 이하일 경우가 인접하다고 하였으므로 상, 하, 좌, 우 외에 대각선으로도 탐색이 가능하다. 즉 8방향으로 탐색이 가능하다.

산봉우리와 "인접하다"를 그림으로 나타낸 것

따라서 BFS를 돌리며 산봉우리가 형성될 수 있는지 아닌지를 판단하며, BFS가 끝난 후 산봉우리가 형성이 된다는 것이 확인되면 1개로 카운팅하면 된다.

 

나는 이를 위해 bool 타입 flag 변수를 만들었고, 현재 탐색 시작점에서 8방향으로 탐색했을 때 현재 탐색 시작점보다 높은 격자가 존재하면 산봉우리가 아닌 것으로 판단해 flag를 flase로 바꿔주었다. 그 후 높이가 같은 격자만 탐색하도록 하였다.

 

위의 그림에서 빨간색 산봉우리 구역을 예로 들면

높이가 4인 지점 (0, 0)에서 높이가 같은 4인 것들만 탐색, 인접 격자들이 현재 탐색 시작점인 4보다 높이가 큰 격자가 없으므로 flag를 true로 바꿔주고 산봉우리로 카운팅해준다.

 

그 다음으로는 3, 2, 1은 인접 격자가 다 자신의 높이 3, 2, 1보다 크므로 산봉우리로 카운팅하지 않는다. 높이가 4인 격자에 귀속된 산봉우리라는 뜻이다.

 

Code

#include<bits/stdc++.h>

using namespace std;

int n, m, cnt = 0;
bool flag;
pair<int, int> dir[8] = {{1, 0}, {1, 1},{0, 1},{-1, 1},{-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
int MAP[101][71];
bool visited[101][71];
queue<pair<int, int>> q;

void BFS(int x, int y) {
    visited[x][y] = true;
    q.push({x, y});

    while(!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0; i < 8; i++) {
            int nxtX = curX + dir[i].first;
            int nxtY = curY + dir[i].second;

            if(nxtX < 0 || nxtY < 0 || nxtX >= n || nxtY >= m) continue;

            if(MAP[x][y] < MAP[nxtX][nxtY]) flag = false;
            //현재 탐색의 기준이 되는 시작점보다 인접한 격자의 높이가 높다면 산봉우리가 아님
            //(가장 높은 격자에 귀속되는 산봉우리.)

            if(!visited[nxtX][nxtY] && MAP[x][y] == MAP[nxtX][nxtY]) {
            	//다음 격자를 방문하지 않았고, 높이가 같다면 탐색.
                visited[nxtX][nxtY] = true;
                q.push({nxtX, nxtY});
            }
        }
    }
}

int main() {
    ios::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 >> MAP[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!visited[i][j]){
                flag = true;
                BFS(i, j);
                if(flag) cnt++;
                //BFS 탐색 결과 산봉우리일 경우 (산봉우리의 가장 높은 지점일 경우) 카운팅.
            }
        }
    }

    cout << cnt << "\n";


    return 0;
}

연휴동안은 여행 때문에 브론즈 V와 브론즈 IV 문제들로 스트릭만 채워서... 4일만에 다시 머리 쓰려니 너무 적응이 안 된다.

1245번: 농장 관리