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

문제 링크

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

1245번: 농장 관리

 

오늘의 생각 : 문제를 잘 읽자!

---

◆문제 해결 및 설명◆

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

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

 

예제 입력을 통해서 분석해 보겠다. 휴리스틱을 사용해 결과만 나타내면 산봉우리는 3개이다.

 

이를 코드로 표현하기 위해 2가지 절차로 구분하였다.

1. 값이 높은 순서대로 위치를 저장해주었다.

2. 값이 높은 곳부터 bfs를 통해서 산봉우리와 연결되어 있으면 0으로 바꾸어 주었다. (=팔방중 자신보다 하나라도 높은 값이 있다)

 

1. 값이 높은 순서대로 위치를 저장해주었다.

정렬의 편의성을 위해서 우선순위 큐를 <tuple>로 선언하였다. 매개변수는 cost, row, col 이므로 cost를 기준으로 가장 큰 값이 top에 오게 된다.

    // push que to (maps[i][j] != 0)
    int cnt = 0;
    priority_queue<tuple<int, int, int>> pq;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (maps[i][j] != 0)
            {
                pq.push({maps[i][j], i, j});
            }
        }
    }

 

2. 값이 높은 곳부터 bfs를 통해서 산봉우리와 연결되어 있으면 0으로 바꾸어 주었다.

우선, 값을 넣어준 pq에서 값을 빼어 해당 위치의 값이 0이 아닌지를 확인해서 bfs를 호출하고 횟수(cnt)를 저장해 주었다.

0인지 확인하는 이유는 bfs 동작과정에서 maps의 산봉우리와 이어져 있는 산을 0으로 만들것이기 때문이다.

    while (!pq.empty())
    {
        int cost, row, col;
        tie(cost, row, col) = pq.top();
        pq.pop();
        // set mountain peak connection value = 0
        if (maps[row][col] != 0)
        {
            bfs(row, col);
            cnt++;
        }
    }

 

이후, bfs의 로직을 만들어 주었다. ny, nx를 통해서 8방을 순회할 수 있게 구현하였고, out of range를 위한 조건문, maps[ny][nx] == 0 인 경우 연산을 줄여주기 위한 조건문 그리고 8방중 자신보다 낮은 값이 있다면 que에 삽입하여 로직을 이어 나갔다. 단 이경우 생각하는 것과 다른 maps가 나온다.

void bfs(int row, int col)
{
    queue<pair<int, int>> que;
    que.push({row, col});
    while (!que.empty())
    {
        tie(row, col) = que.front();
        que.pop();
        if (visited[row][col])
        {
            continue;
        }
        visited[row][col] = 1;

        for (int i = 0; i < 8; i++)
        {
            int ny = row + dy[i];
            int nx = col + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M)
            {
                continue;
            }
            if (!maps[ny][nx]) // maps[ny][nx] == 0
            {
                visited[ny][nx] = 1;
                continue;
            }
            if (maps[row][col] >= maps[ny][nx])
            {
                que.push({ny, nx});
            }
        }
        maps[row][col] = 0;
    }
}

아래 산들까지 없어져 버리는 것을 볼 수 있는데, 이는 두 산이 대각선으로 이어져 있기 때문이다.

하지만, 산봉우리는 살아 있으므로 연산은 제대로 구현 된다! 이후 bfs 호출 횟수를 출력하여 답을 제출하였다.

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
vector<vector<int>> maps;
vector<vector<int>> visited;
int dy[]{1, -1, 0, 0, 1, -1, 1, -1};
int dx[]{0, 0, 1, -1, 1, -1, -1, 1};

void bfs(int row, int col)
{
    queue<pair<int, int>> que;
    que.push({row, col});
    while (!que.empty())
    {
        tie(row, col) = que.front();
        que.pop();
        if (visited[row][col])
        {
            continue;
        }
        visited[row][col] = 1;

        for (int i = 0; i < 8; i++)
        {
            int ny = row + dy[i];
            int nx = col + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M)
            {
                continue;
            }
            if (!maps[ny][nx]) // maps[ny][nx] == 0
            {
                visited[ny][nx] = 1;
                continue;
            }
            if (maps[row][col] >= maps[ny][nx])
            {
                que.push({ny, nx});
            }
        }
        maps[row][col] = 0;
    }
}

int main()
{
    cin >> N >> M;
    maps = vector<vector<int>>(N, vector<int>(M));
    visited = vector<vector<int>>(N, vector<int>(M));
    for (vector<int> &i : maps)
    {
        for (int &j : i)
        {
            cin >> j;
        }
    }

    // push que to (maps[i][j] != 0)
    int cnt = 0;
    priority_queue<tuple<int, int, int>> pq;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (maps[i][j] != 0)
            {
                pq.push({maps[i][j], i, j});
            }
        }
    }

    while (!pq.empty())
    {
        int cost, row, col;
        tie(cost, row, col) = pq.top();
        pq.pop();
        // set mountain peak connection value = 0
        if (maps[row][col] != 0)
        {
            bfs(row, col);
            cnt++;
        }
    }

    cout << cnt;
}