1113번 수영장 만들기

 

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

 

핵심은 높이를 2부터 입력된 최대 높이까지 각각 하나씩 채워주는 것이다.

 

main() 함수 내의 for문 h의 의미는 "h보다 작은 곳을 찾아 높이를 딱 h까지 채우겠다."라는 의미로 해석하면 된다.

 

또한, dfs가 수행될 때, 바깥 쪽(행과 열이 0 또는 R - 1 또는 C - 1)일 때는

 

바깥 쪽으로 흘러내리므로, 이때는 답 구하는 연산에 셈하지 않는다.(bool형 변수인 stop 활용하였음)

 

 

 

1. 입력된 값들 중 최댓값 구하기(최대 높이 = H)

 

2. 2 ~ H 각각 수행 → h

 

3. h보다 미만인 곳을 찾아 vector에 넣어준다.

 

4. vector를 활용하여, dfs 수행

 

5. 바깥 쪽일 경우 답 구하는 연산에서 제외

 

6. 바깥 쪽이 아닐 경우, dfs가 return 해주는 값을 더해준다. 

즉, return 해주는 값은 하나의 연결요소를 이루는 좌표의 개수이다.

아래 그림 예

 

 

 

 

 

 

 

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 52

int R, C, H, answer;
int m[MAX][MAX];
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
bool used[MAX][MAX], stop = false;

int dfs(int r, int c, int h)
{
    used[r][c] = true;

    int ret = 1;

    for (int i = 0; i < 4; i++) {
        int y = r + dy[i];
        int x = c + dx[i];
        if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] >= h || used[y][x]) {
            continue;
        }

        if (y == 0 || x == 0 || y == R - 1 || x == C - 1) {
            stop = true;
            /*
            처음에는 break;도 구현했었는데, break를 해버리면, 
            main() 내에서 if(!used[r][c])가 실행되어 버릴 수 있다.
            같은 연결요소임에도 불구하고, break를 해버리고, used[r][c]에 true가 적용이
            안됐으므로, 실행된다.

            관련 반례
            3 5
            55555
            32123
            33233
            답 : 1
            오답 : 2
            사유 : break;가 있다면, (1, 3)까지 셈하게 된다.(h = 3)
            */
        }

        ret += dfs(y, x, h);
    }

    return ret;
}

vector<pair<int, int> > getVectorUnderHeight(int h)
{
    vector<pair<int, int> > ret;

    for (int i = 1; i < R - 1; i++) {
        for (int j = 1; j < C - 1; j++) {
            if (m[i][j] < h) {
                ret.push_back({ i, j });
            }
        }
    }

    return ret;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%1d", &m[i][j]);
            H = max(H, m[i][j]);
        }
    }

    for (int h = 2; h <= H; h++) {

        memset(used, false, sizeof(used));
        vector<pair<int, int> > v = getVectorUnderHeight(h);

        int cnt = 0;
        for (auto i : v) {
            int r = i.first, c = i.second;
            stop = false;
            if (!used[r][c]) {
                int g = dfs(r, c, h);
                if (!stop) {
                    cnt += g;
                }
            }
        }

        answer += cnt;
    }

    printf("%d\n", answer);

    return 0;
}