[백준 1245] 농장 관리

단 한번의 BFS 또는 DFS로 끝내는 방법을 생각하다가 실패해서 구글링으로 힌트를 얻음.

 

알고보니 특정 높이의 봉우리 영역을 탐색하기 위해

각 높이마다 개별적으로 BFS를 진행해주어야했음

 

 

 

위와 같이 특정 높이의 봉우리마다 BFS를 진행해줘 해당 봉우리가 포함된 영역을 찾아주면 되는 것이었음.

 

---

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

int N, M;
int map[101][71];
queue<pair<int, int>> q;

int checky[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int checkx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

bitset<71> visited[101];

// 특정 높이에 해당하는 봉우리 영역을 탐색
// 주변보다 낮은 영역이면 flag false 체크
// 봉우리 영역이 주변보다 높은 영역이면 flag true 유지
int solve(int y, int x, int height)
{
    bool flag = true;
    q.push(make_pair(y, x));
    visited[y][x] = 1;

    int newy, newx;
    while (!q.empty())
    {
        y = q.front().first;
        x = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++)
        {
            newy = y + checky[i];
            newx = x + checkx[i];

            // 범위 넘어가면 스킵
            if (newy < 0 || newx < 0 || newy >= N || newx >= M)
            {
                continue;
            }

            // 만약 주변에 더 높은 봉우리가 있으면 산봉우리 아니니 false로 변경해놓고
            // 영역 탐색은 계속 진행
            if (map[newy][newx] > height)
            {
                flag = false;
            }

            // 아직 방문안했고 나랑 같은 높이의 봉우리이면
            // 같은 높이의 영역이므로 계속 큐에 집어넣으면서 영역 탐색 진행
            if (!visited[newy][newx] && map[newy][newx] == height)
            {
                visited[newy][newx] = 1;
                q.push(make_pair(newy, newx));
            }
        }
    }

    // 산봉우리면 산봉우리 추가
    if (flag)
        return 1;
    else
        return 0;
}

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

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> map[i][k];
        }
    }

    int ans = 0;

    // 각 높이별로 영역 확인해주기
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            // 현재 조사하고 있는 높이의 영역들을 구하기 위해 해당 위치의 높이까지 같이 넘겨주기
            // solve 함수는 인자로 받은 높이에 해당하는 영역을 구해줌
            // 만약 봉우리영역이면 return 1 아니면 return 0
            if (!visited[i][k])
            {
                ans += solve(i, k, map[i][k]);
            }
        }
    }

    cout << ans;

    return 0;
}