[BAEKJOON] 1113. 수영장 만들기

Posted on January 23, 2021

문제 :

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661 61116 16661

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

입력 :

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

출력 :

첫째 줄에 문제의 정답을 출력한다.

풀이 :

문제 접근에 굉장히 오랜 시간이 소요된 문제였다.

우선 물을 담을 때 동서남북 4방향이 모두 막혀있다는 것을 확인하는 방법만 접근하려고 노력하는 바람에 문제를 유연하게 바라보지 못한 점이 시간을 많이 잡아먹은 문제였던 것 같다.

문제는 접근방법만 알아낸다면 구현은 크게 어렵지 않다.

내가 접근한 방법은 우선 각 땅의 높이는 1이상 9이하이기 때문에 물은 2부터 차례로 채워나가는 것이다.

단, 물을 채워나가는데 한 가지 조건을 걸어주어야 한다. bfs로 해당 영역의 물을 채워나가는 경우 바깥 인덱스(배열 처음, 마지막 행과 열)로 누출되어 버리는 경우에는 채운 물 양을 합해주지 않는 것이다.

이렇게 되면 각 반복문 수행 때마다 모든 칸은 일정 물 높이 이상으로 모두 배열 값이 변하는 동시에 누출되지 않고 담기는 물의 양만 체크할 수 있게 된다.

문제를 유연하게 바라보는 연습이 조금 필요한 듯 하다.

코드 :

코드 보기/접기

#include <iostream>
#include <queue>
#include <utility>

#define pii pair<int, int>

using namespace std;
int n, m, map[50][50], di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

int bfs(int x, int y, int height) {
    queue<pii > q;
    int count = 1;
    bool leak = false;
    q.push(pii(x, y));
    map[x][y] = height;

    while (!q.empty()) {
        int curx = q.front().first, cury = q.front().second;
        q.pop();
        if (curx == 0 || curx == n - 1 || cury == 0 || cury == m - 1) leak = true;
        for (int k = 0; k < 4; k++) {
            int cmpx = curx + di[k], cmpy = cury + dj[k];
            if (cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= m) continue;
            if (map[cmpx][cmpy] < height) {
                q.push(pii(cmpx, cmpy));
                map[cmpx][cmpy] = height;
                count++;
            }
        }
    }
    return ((leak) ? 0 : count);
}

int main() {
    char num;
    int i, j, answer = 0;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> num;
            map[i][j] = num - '0';
        }
    for (int k = 2; k < 10; k++)
        for (i = 0; i < n; i++)
            for (j = 0; j < m; j++)
                if (map[i][j] < k) answer += bfs(i, j, k);

    cout << answer << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++