【백준】- 23545. Liquid Cats

문제

본 문제는 외국어 문제이기에, 제가 문제 번역을 작성해 두었습니다. 아래의 링크를 참고해 주세요!

https://www.acmicpc.net/board/view/108204

글 읽기 - 【번역】23545. 고양이 액체설

좀 발 번역이라... 죄송합니다. 간단하게 요약하자면, 덩어리 하나를 격자의 아래쪽에 최대한 쑤셔 넣고, 그때의 덩어리가 차지하는 높이가 최소가 되려면 어떻게 해야 할지 생각해 보아야 하는 문제입니다.

풀이

단순히 아래쪽 칸부터 채워나갈 수 있다면 좋겠지만, 고양이의 몸이 둘로 분리될 수 있기에 아래쪽 칸을 채우지 않는 경우가 최적일 수도 있습니다. 아래의 예시의 경우, 고양이가 $4$ 칸을 차지한다고 했을 때, 왼쪽 그림처럼 무조건 아래쪽 칸부터 채울 경우 고양이의 몸이 둘 이상이게 됩니다. 그래서 어쩔 수 없이 오른쪽 그림처럼 고양이를 넣어야 하며, 이 경우 행의 번호는 $2$ 가 됩니다.

고양이를 배치할 수 있는 행의 번호를 고정시킨다면?

이대로 문제를 풀기에는 너무 어렵습니다. 문제를 좀 더 단순하게 바꿔 봅시다. 아래와 같이 조건을 제한한다면 좀 더 접근이 쉬워질까요?

• 고양이를 배치할 수 있는 행의 번호는 무조건 $x$ 이상이어야 할 때, 고양이를 수조에 넣을 수 있을까?

$x = 2$, $x = 3$ 를 예로 들어 볼까요?

파란색 영역은 고양이를 넣을 수 있는 전체 영역, 노란색 영역은 장애물에 의해 분리되어 나누어진 영역입니다. 고양이의 몸은 무조건 하나여야만 하므로, 고양이가 들어갈 영역을 고를 때는 하나의 노란색 영역만을 고를 수 있게 됩니다.

$x = 2$ 의 경우에는 가장 큰 노란색 영역의 크기가 $13$ 칸이기 때문에 충분히 고양이를 넣을 수 있지만, $x = 3$ 의 경우에는 가장 큰 노란색 영역의 크기가 $3$ 칸이기에, 고양이를 넣을 수 없습니다.

 

이렇게 $x$ 값을 고정시킨 후, 영역의 크기를 구하면 고양이를 넣을 수 있는지 확실하게 알 수 있습니다! 이제 $x$ 값을 $1$ 부터 $n$ 까지 정하고, 차례대로 영역을 구해 배치가 가능한지의 여부를 판별한다면, 정답을 구할 수 있을 것입니다. 영역의 크기를 구하는 것은 깊이 우선 탐색 또는 너비 우선 탐색 알고리즘을 이용해, 인접한 칸을 방문해 가면서 영역의 개수를 세면 됩니다.

 

다만 이 풀이의 시간복잡도는 $O(n^2m)$ 로, 문제를 풀기에는 너무 시간이 오래 걸립니다. 더 효율적으로 문제를 풀 수 있는 방법은 없을까요?

행의 번호를 매개 변수 탐색으로 정한다면?

$x$ 의 값이 커질수록, 문제에서 요구하는 큰 $x$ 값을 얻을 수 있지만, 사용할 수 있는 파란 영역이 좁아지므로 고양이를 수조에 넣는 것이 불리해집니다. 따라서, $x$ 값을 적절히 조절하면서 $x$ 의 값을 최대화해야 합니다. 이는 매개 변수 탐색을 이용해 접근해 볼 수 있습니다. $x$ 값으로 가능한 범위를 정해 두고, 탐색을 할 때마다 범위를 절반으로 줄여 나가는 것이죠. 아래의 발상을 이용할 수 있습니다.

• 만약 $x = t$ 일 때 고양이를 수조에 넣을 수 있다면, $t$ 값을 더 증가시켜볼 수 있습니다. $x < t$ 인 경우는 비효율적인 경우가 되므로, 항상 정답이 아니게 됩니다.
• 만약 $x = t$ 일 때 고양이를 수조에 넣을 수 없다면, $t$ 값을 감소시켜야 합니다. 이에 따라 $x \ge t$ 인 경우는 고양이를 넣을 수 없는 경우이므로, 항상 정답이 아니게 됩니다.

이렇게 행의 번호를 매개 변수 탐색으로 정해 주고, 각 행의 번호마다 영역의 개수를 세 준다면, $x$ 값을 시도해 보는 횟수를 크게 줄일 수 있습니다. 매개 변수 탐색을 이용한 경우, 시간복잡도는 $O(n\log nm)$ 으로, 시간 내에 충분히 문제를 풀 수 있게 됩니다!

코드

• C++17

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Loc {
    int r, c;
};

char bowl[1002][1002];
bool visited[1002][1002];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int R, C, K;

int get_area(int limit_row, Loc start_location) {
    if (visited[start_location.r][start_location.c] || bowl[start_location.r][start_location.c] == '#') {
        return 0;
    }
    
    int area = 0;
    queue<Loc> q;
    q.push({start_location.r, start_location.c});
    visited[start_location.r][start_location.c] = true;
    
    while (!q.empty()) {
        Loc cur = q.front();
        q.pop();
        area += 1;
        
        for (int i = 0; i < 4; i++) {
            int r = cur.r + dr[i];
            int c = cur.c + dc[i];
            
            if (limit_row <= r && r <= R && 1 <= c && c <= C && !visited[r][c] && bowl[r][c] == '.') {
                visited[r][c] = true;
                q.push({r, c});
            }
        }
    }
    
    return area;
}

bool is_possible(int limit_row) {
    fill(&visited[1][1], &visited[R][C + 1], false);
    int max_area = 0;
    
    for (int r = limit_row; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            max_area = max(max_area, get_area(limit_row, {r, c}));
        }
    }
    
    if (max_area >= K) {
        return true;
    }
    
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> R >> C >> K;
    
    for (int r = 1; r <= R; r++) {
        cin >> (bowl[r] + 1);
    }
    
    int start = 1;
    int end = R;
    int mid;
    
    while (start <= end) {
        mid = (start + end) / 2;
        
        if (is_possible(mid)) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    
    if (end == 0) {
        cout << -1;
    } else {
        cout << end;
    }
}