백준 4001 미노타우르스 미궁

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

 

거의 반 년 동안 큐에 들어있던 문제인데 도저히 못 풀겠더라

그동안 못 푼 문제 풀이 까기에 대한 강박적인 거부감이 있었는데, 최근에 이런저런 대화와 생각을 거치며 거부감이 줄어서 풀이를 찾아봤다. 

https://leo630.tistory.com/138

BOJ 4001 - 미노타우르스 미궁

 

최소 정사각형을 찾는다는 목표와 O(wh log w) 정도가 돌 제한에서 이분 탐색 냄새가 진하게 났는데, 처음 들어간 잘못된 방향에서 헤어나오질 못 했다. 격자에서 연결된다 <-> 양끝 벽이 안 이어진다는 여러 번(https://www.acmicpc.net/problem/24515, https://www.acmicpc.net/problem/34221) 썼던 관찰인데 못 떠올린 게 많이 아쉽다. 생각해보니까 24515도 풀이 까고 풀었던 것 같다.. 이 관찰을 못 한 탓에 임의의 정사각형을 잡았을 때 양 끝 점이 끊기는지 판별이 상수 시간에 절대 안 된다고 생각해서 크기 같은 정사각형을 한번에 어떻게 잘 처리해야된다고 생각했는데, 정사각형의 좌표가 고정되지 않으면 크기에 대한 단조성이 없어져서 어떻게 할지 도저히 감이 안 왔다. 먼가 플로우일지도 모른다는 생각도 들고.. 한 번 꼬이기 시작하니까 답이 없더라

 

#include <bits/stdc++.h>
using namespace std;
 
int chk[1515][1515], lchk[1515][1515], rchk[1515][1515], w, h;
char mp[1515][1515];
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 
void dfs(int x, int y, int (*c)[1515]){
    c[y][x] = 1;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (0 <= nx and nx <= w+1 and 0 <= ny and ny <= h+1 and mp[ny][nx] == '#' and !c[ny][nx])   
            dfs(nx, ny, c);
    }
}
 
int sum(int xs, int ys, int xe, int ye, int (*A)[1515]) {
    if (!xs and !ys) return A[ye][xe];
    if (!xs) return A[ye][xe] - A[ys-1][xe];
    if (!ys) return A[ye][xe] - A[ye][xs-1];
    return A[ye][xe] - A[ye][xs-1] - A[ys-1][xe] + A[ys-1][xs-1];
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> w >> h;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++){
            cin >> mp[i][j];
            chk[i][j] = mp[i][j] == '#';
        }
    for (int i = 2; i <= h+1; i++) mp[i][0] = '#';
    for (int i = 0; i <= h-1; i++) mp[i][w+1] = '#';
    for (int i = 2; i <= w+1; i++) mp[0][i] = '#';
    for (int i = 0; i <= w-1; i++) mp[h+1][i] = '#';
    dfs(2, 0, rchk);
    dfs(0, 2, lchk);
    
    for (int i = 1; i <= h+1; i++) {
        chk[i][0] += chk[i-1][0];
        lchk[i][0] += lchk[i-1][0];
        rchk[i][0] += rchk[i-1][0];
    }
    for (int i = 1; i <= w+1; i++){
        chk[0][i] += chk[0][i-1];
        lchk[0][i] += lchk[0][i-1];
        rchk[0][i] += rchk[0][i-1];
    }
    for (int i = 1; i <= h+1; i++)
        for (int j = 1; j <= w+1; j++){
            chk[i][j] += chk[i-1][j] + chk[i][j-1] - chk[i-1][j-1];
            lchk[i][j] += lchk[i-1][j] + lchk[i][j-1] - lchk[i-1][j-1];
            rchk[i][j] += rchk[i-1][j] + rchk[i][j-1] - rchk[i-1][j-1];
        }
    int ans = 1e9, x = -1, y = -1;
    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            if (mp[i][j] == '#' or (i == 1 and j == 1) or (i == h and j == w)) continue;
            int yes = 1, no = max(w, h);
            while (yes+1 < no) {
                int m = yes+no >> 1;
                if (j+m-1 <= w and i+m-1 <= h and (j+m-1 < w or i+m-1 < h) and !sum(j, i, j+m-1, i+m-1, chk))
                    yes = m;
                else
                    no = m; 
            }
            if (!sum(j-1, i-1, j+yes, i+yes, lchk) or !sum(j-1, i-1, j+yes, i+yes, rchk)) continue;
            no = 0;
            while (no+1 < yes) {
                int m = no+yes >> 1;
                if (sum(j-1, i-1, j+m, i+m, lchk) and sum(j-1, i-1, j+m, i+m, rchk))
                    yes = m;
                else
                    no = m;
            }
            if (yes < ans) ans = yes, x = j, y = i;
        }
    }
    if (x == -1) cout << "Impossible";
    else cout << ans << ' ' << x << ' ' << y;
}