[Pro] 섬 지키기

문제

해수면 상승으로부터 섬을 지키기 위해 구조물을 설치하려고 한다. 섬은 N × N 크기의 정사각형 모양이며, 1 × 1 크기의 정사각형 지역들로 이루어져 있다. 각 지역에는 고도가 주어진다. 설치할 구조물은 1 × M 크기이며, 1 × 1 크기의 부분 M개가 일렬로 연결되어 있다. 구조물의 각 부분에는 높이가 주어진다.

구조물은 섬의 연속한 M개 지역 위에 가로 또는 세로 방향으로 설치할 수 있다. 구조물의 방향을 뒤집어 설치하는 것도 가능하다. 구조물을 설치했을 때, 구조물의 각 부분 높이와 해당 지역의 기존 고도를 더한 값이 모두 같아야 한다. 이 조건을 만족하는 경우에만 구조물을 설치할 수 있다.

구조물을 설치할 수 있는 경우의 수를 셀 때, 구조물이 놓이는 지역들이 모두 같으면 구조물의 방향이 다르더라도 같은 경우로 취급한다. 설치 지역이 하나라도 다르면 다른 경우로 취급한다.

해수면이 mSeaLevel만큼 상승하면, 고도가 mSeaLevel보다 낮으면서 바다와 연결된 지역은 물에 잠긴다.

바닷물은 섬의 바깥에서 들어오며, 상하좌우로 인접한 지역을 따라 이동한다. 따라서 고도가 해수면보다 낮더라도 높은 지역들에 둘러싸여 바다와 연결되지 않은 지역은 잠기지 않는다.

구조물 한 개를 적절한 위치에 설치하여, 해수면 상승 후에도 물에 잠기지 않고 남는 지역의 개수를 최대화해야 한다.

maxArea()에서 구조물은 결과를 계산하기 위해 임시로 설치하는 것이며, 실제 섬의 고도는 변경되지 않는다. 다음 함수 호출에서도 섬은 init()에서 주어진 원래 상태를 유지한다.

구현해야 하는 API는 다음과 같다.

void init(int N, int mMap[20][20]);
int numberOfCandidate(int M, int mStructure[5]);
int maxArea(int M, int mStructure[5], int mSeaLevel);

`void init(int N, int mMap[20][20])`

각 테스트 케이스의 처음에 호출된다.

N × N 크기의 섬과 각 지역의 고도 정보를 전달받아 초기화한다.

Parameter	설명
`N`	섬의 한 변의 길이 (`5 ≤ N ≤ 20`)
`mMap`	섬의 각 지역의 고도 (`1 ≤ mMap[i][j] ≤ 5`)

`int numberOfCandidate(int M, int mStructure[5])`

크기가 1 × M인 구조물 mStructure를 한 개 설치할 때, 설치 가능한 경우의 수를 반환한다.

구조물은 가로 또는 세로로 설치할 수 있고, 반대 방향으로 뒤집어 설치할 수도 있다. 설치 후 구조물이 놓인 모든 지역의 최종 고도가 같아야 한다.

설치 지역이 모두 동일하면 같은 경우로 취급하며, 설치 지역이 하나라도 다르면 다른 경우로 취급한다.

Parameter	설명
`M`	구조물의 길이 (`1 ≤ M ≤ 5`)
`mStructure`	구조물 각 부분의 높이 (`1 ≤ mStructure[i] ≤ 5`)

Return	설명
`int`	구조물을 설치할 수 있는 경우의 수

`int maxArea(int M, int mStructure[5], int mSeaLevel)`

구조물 mStructure를 한 개 설치한 뒤 해수면이 mSeaLevel만큼 상승한다고 하자.

구조물을 설치할 수 있는 모든 경우 중, 바다에 잠기지 않고 남아 있는 지역의 개수가 최대가 되도록 설치했을 때의 지역 개수를 반환한다.

구조물을 설치할 수 있는 방법이 하나도 없다면 -1을 반환한다.

이 함수에서 구조물은 실제로 설치되지 않는다. 함수가 종료된 뒤 섬의 각 지역 고도는 init()에서 주어진 값 그대로 유지되어야 한다.

Parameter	설명
`M`	구조물의 길이 (`1 ≤ M ≤ 5`)
`mStructure`	구조물 각 부분의 높이 (`1 ≤ mStructure[i] ≤ 5`)
`mSeaLevel`	해수면의 상승 높이 (`1 ≤ mSeaLevel ≤ 10`)

Return	설명
`int`	구조물을 최적으로 설치했을 때 바다에 잠기지 않고 남는 지역의 최대 개수. 설치 가능한 위치가 없으면 `-1`

제약사항은 다음과 같다.

각 테스트 케이스의 시작 시 init()이 한 번 호출된다.
섬의 한 변의 길이 N은 5 이상 20 이하이다.
섬의 각 지역의 고도는 1 이상 5 이하이다.
구조물의 길이 M은 1 이상 5 이하이다.
구조물 각 부분의 높이는 1 이상 5 이하이다.
mSeaLevel은 1 이상 10 이하이다.
한 테스트 케이스에서 numberOfCandidate()는 최대 150,000번 호출된다.
한 테스트 케이스에서 maxArea()는 최대 50번 호출된다.
한 테스트 케이스에서 모든 maxArea() 호출에 대해, 주어진 구조물 mStructure를 설치할 수 있는 경우의 수의 총합은 5,000 이하이다.
힙 메모리와 정적 메모리의 합은 256 MB 이내이며, 스택 메모리는 1 MB 이내이다.

설명

numberOfCandidate() 가 최대 150.000번 호출된다는 점에 주목해야 한다.

한 테스트 케이스에서 모든 maxArea() 호출에 대해, 주어진 구조물 mStructure를 설치할 수 있는 경우의 수의 총합은 5,000 이하이다.

이 문장에 대한 의미를 살펴보기 위해 maxArea()의 동작을 구체화하면 다음과 같다.

설치 가능한 후보 위치 하나를 고른다.
구조물을 임시로 설치한다.
잠기지 않은 면적을 계산한다.
원상복구한다.

면적을 계산하는 알고리즘의 시간복잡도를 $O(N^2)$ 이라고 해도, 연산 횟수는 5000 * 20 * 20 = 2,000,000번으로 시간 제한을 벗어나지 않는다.

가장 먼저 할 수 있는 생각은 모든 위치에 일단 설치해보는 것이다. 구조물 길이가 M이면 가로, 세로로 연속한 M칸에 구조물을 설치하고, 지역 높이와 구조물 높이가 전부 같은지를 확인한다. 반대로 설치하는 경우도 확인해야 한다.

침수된 지역은 BFS로 구하면 될 것이다.

완전탐색 방식으로 구조물을 설치하는 방식의 시간복잡도는 후보 위치를 찾을 때 $O(N^2)$ , 설치 가능 여부를 검사할 때 $O(M)$ 으로, 총 $O(N^2M)$ 이다.

numberOfCandidate()는 최대 150,000번 호출되는데, 이 경우 최악의 연산 수는 150,000 * 20 * 20 * 5 = 300,000,000번이 나오게 되어 TLE이다.

maxArea()는 최대 50번 호출되므로 아직까지는 문제가 되지 않는다.

섬은 init() 이후 변하지 않는다. 실제로 구조물을 설치하지 않기 때문이다. 여기서 numberOfCandidate()가 호출될 때마다 섬을 계속 탐색하는 것이 어색하다고 생각할 수 있다.

즉, 반복되는 탐색을 init()으로 옮긴다. 길이 2 ~ 5의 모든 가로 및 세로 구간에 대하여 어떤 구조물이 맞을지를 미리 찾는다.

이때 기준이 되는 것은 지형의 높이 변화이다. 지형의 높이가 1, 2, 3 인 것과 2, 3, 4인 것은 모두 구조물 [3, 2, 1]을 설치할 수 있다. 중요한 것은 두 지형의 높이 변화가 +1, +1이라는 것이다.

일반화를 해 보자. 편의 상 길이 3의 가로 구간을 예로 든다.

지형의 높이가 h0, h1, h2 이고, 구조물이 [s0, s1, s2] 라면 설치 가능 조건은 h0 + s0 = h1 + s1 = h2 + s2 이다. 앞의 식만 보면 s0 - s1 = h1 - h0 가 성립하는데, 이는 실제로 구조물의 높이를 더하지 않고 지형의 인접 높이 차가 구조물의 반대쪽 인접 높이 차가 같은지를 보면 된다는 것을 의미한다.

동일한 패턴을 가지는 구간의 시작 좌표와 방향(가로, 세로)을 저장한다.

기존에는 numberOfCandidate()의 시간복잡도가 $O(N^2M)$ 이었다면, 미리 전처리를 하면 구조물의 차이만 계산하고 그 패턴에 해당하는 후보만 가져오면 되므로 $O(M)$ 이 된다.

이제 남은 문제는 패턴에 대한 후보들을 저장하기 위해 패턴을 어떻게 표현할 것인가이다. 패턴의 형태는 [+1, -2], [+2, -1, +2]와 같은 형태이므로 먼저 map<vector<int>> 를 떠올릴 수 있다.

다만 패턴의 범위는 매우 작기 때문에 간단한 방법으로 하나의 숫자로, 배열 인덱스로 사용하도록 바꿀 수 있다. 높이 차로 가능한 수들은 -4 ~ 4이다. 5를 더하면 1 ~ 9가 된다. 이를 이어붙여 바로 인덱스로 사용할 수 있다. 예를 들어 [+1, +1]은 66, [+2, -1, +1]은 746이 된다.

코드

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX_N 20
#define MAX_HASH 9999

int N;

// 바다 영역을 표현하기 위해 섬의 외곽에 1칸의 여유 공간을 둔다.
int map[MAX_N + 2][MAX_N + 2]; // 원본 섬
int tmpMap[MAX_N + 2][MAX_N + 2]; // 임시 섬

struct Candidate {
    int r; // 설치 시작 행
    int c; // 설치 시작 열
    bool horizontal; // 구조물이 가로 방향인가
    bool reverse; // 구조물을 뒤집어서 설치하는가
};

vector<Candidate> candidate[MAX_HASH + 1];

// 높이 차이 패턴을 하나의 숫자로 변환한다.
// 높이 차이는 -4 ~ 4이므로 +5를 적용해 1 ~ 9로 표현하고 이어붙인다.
int getHeightDiffHash(int r, int c, int length, bool horizontal, bool reverse) {
    int hash = 0;

    for (int i = 0; i < length - 1; i++) {
        int diff;

        if (horizontal) {
            if (!reverse)
                diff = map[r][c + i + 1] - map[r][c + i];
            else
                diff = map[r][c + length - i - 2] - map[r][c + length - i - 1];
        }
        else {
            if (!reverse)
                diff = map[r + i + 1][c] - map[r + i][c];
            else
                diff = map[r + length - i - 2][c] - map[r + length - i - 1][c];
        }

        hash = hash * 10 + diff + 5;
    }

    return hash;
}

void init(int n, int mMap[20][20]) {
    N = n;

    for (int i = 0; i <= MAX_HASH; i++)
        candidate[i].clear();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i + 1][j + 1] = mMap[i][j];
            tmpMap[i + 1][j + 1] = mMap[i][j];
        }
    }

    // 길이 2 ~ 5의 모든 가로, 세로 구간을 높이 차이 패턴별로 저장한다.
    for (int length = 2; length <= 5; length++) {
        // 가로 방향
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c + length - 1 <= N; c++) {
                int hash = getHeightDiffHash(r, c, length, true, false);
                candidate[hash].push_back({r, c, true, false});

                // 같은 지형을 반대 방향에서 읽은 패턴도 저장한다.
                int reverseHash = getHeightDiffHash(r, c, length, true, true);

                // 두 패턴이 같으면 동일한 설치 위치를 중복 저장하지 않는다.
                if (hash != reverseHash)
                    candidate[reverseHash].push_back({r, c, true, true});
            }
        }

        // 세로 방향
        for (int r = 1; r + length - 1 <= N; r++) {
            for (int c = 1; c <= N; c++) {
                int hash = getHeightDiffHash(r, c, length, false, false);
                candidate[hash].push_back({r, c, false, false});

                int reverseHash = getHeightDiffHash(r, c, length, false, true);

                if (hash != reverseHash)
                    candidate[reverseHash].push_back({r, c, false, true});
            }
        }
    }
}

// 구조물의 높이 차이 패턴으로 설치 가능한 후보 개수를 조회한다.
int numberOfCandidate(int M, int mStructure[5]) {
    // 길이가 1이면 모든 지역에 설치할 수 있다.
    if (M == 1)
        return N * N;

    int hash = 0;

    for (int i = 0; i < M - 1; i++)
        hash = hash * 10 + (mStructure[i] - mStructure[i + 1] + 5);

    return candidate[hash].size();
}

bool visited[MAX_N + 2][MAX_N + 2];

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};

// 바깥 바다에서 BFS를 시작해 침수되지 않은 지역 개수를 반환한다.
int getArea(int seaLevel) {
    queue<pair<int, int>> q;

    // 섬 외부를 바다 시작점으로 설정한다.
    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
            if (i == 0 || i == N + 1 || j == 0 || j == N + 1) {
                q.push({i, j});
                visited[i][j] = true;
            }
            else {
                visited[i][j] = false;
            }
        }
    }

    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 1 || nr > N || nc < 1 || nc > N)
                continue;

            if (visited[nr][nc])
                continue;

            // 해수면보다 낮은 지역으로만 바닷물이 이동한다.
            if (tmpMap[nr][nc] < seaLevel) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }

    int result = 0;

    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (!visited[r][c])
                result++;
        }
    }

    return result;
}

// 후보 위치에 구조물을 임시 설치한다.
// 설치 가능한 후보이므로 구조물이 놓인 모든 칸의 최종 높이는 같다.
void install(Candidate c, int M, int mStructure[5]) {
    int height;

    if (c.horizontal) {
        if (!c.reverse)
            height = map[c.r][c.c] + mStructure[0];
        else
            height = map[c.r][c.c + M - 1] + mStructure[0];

        for (int i = 0; i < M; i++)
            tmpMap[c.r][c.c + i] = height;
    }
    else {
        if (!c.reverse)
            height = map[c.r][c.c] + mStructure[0];
        else
            height = map[c.r + M - 1][c.c] + mStructure[0];

        for (int i = 0; i < M; i++)
            tmpMap[c.r + i][c.c] = height;
    }
}

// 다음 후보를 확인하기 위해 구조물을 설치한 위치만 원상복구한다.
void restore(Candidate c, int M) {
    if (c.horizontal) {
        for (int i = 0; i < M; i++)
            tmpMap[c.r][c.c + i] = map[c.r][c.c + i];
    }
    else {
        for (int i = 0; i < M; i++)
            tmpMap[c.r + i][c.c] = map[c.r + i][c.c];
    }
}

int maxArea(int M, int mStructure[5], int mSeaLevel) {
    int result = -1;

    // 길이가 1이면 모든 지역에 하나씩 설치해본다.
    if (M == 1) {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                tmpMap[r][c] = map[r][c] + mStructure[0];
                result = max(result, getArea(mSeaLevel));
                tmpMap[r][c] = map[r][c];
            }
        }

        return result;
    }

    int hash = 0;

    for (int i = 0; i < M - 1; i++)
        hash = hash * 10 + (mStructure[i] - mStructure[i + 1] + 5);

    // init()에서 미리 구한 설치 가능한 후보만 확인한다.
    for (Candidate c : candidate[hash]) {
        install(c, M, mStructure);
        result = max(result, getArea(mSeaLevel));
        restore(c, M);
    }

    return result;
}

시간복잡도

init()에서 모든 길이의 가로, 세로 구간을 탐색하며 해시값을 계산하므로 $O(N^2M)$ , numberOfCandidate()는 구조물 해시를 계산하고 배열을 조회하므로 $O(M)$ 이다. maxArea()에서 설치 가능한 후보 영역의 수를 C라고 할 때, 각 후보에 대해 구조물을 설치하고 BFS를 수행하므로 $O(CN^2)$ 이다.

공간복잡도

섬, visited, 후보를 저장하는 배열에서 공간복잡도는 $O(N^2)$ 이다.