BOJ_1915 가장 큰 정사각형

TOC {:toc}

이 글은 백준 온라인 저지의 1915번 문제를 자바스크립트(JavaScript)로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.26

메모리	시간	코드 길이
40008 KB	332 ms	692 B

단계	시작 시각	끝난 시각
문제 이해	16:05:51	16:06:53
풀이 생각	16:06:55	16:25:57
코딩	23:22:42	23:40:40
디버깅	23:40:59	00:37:06

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [NM, ...lines] = input;
const [N, M] = NM.split(" ").map((n) => parseInt(n));
const matrix = lines.map((line) => [...line].map((n) => parseInt(n)));
const dist = matrix.map((line) => [...line]);

function main() {
    for (let i = 1; i < N; i += 1) {
        for (let j = 1; j < M; j += 1) {
            if (!matrix[i][j]) {
                continue;
            }
            dist[i][j] = Math.min(dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1]) + 1;
        }
    }

    const max = Math.max(...dist.map((row) => Math.max(...row)));
    return max ** 2;
}

console.log(main());

아이디어 & 풀이

주어진 행렬을 순회하면서 이전의 값을 이용해 (i, j)까지의 행렬중 가장 큰 정사각형의 변의 길이를 정한다.

즉 dist(dp)[i][j]는 (i, j)을 오른쪽 아래 꼭지점으로 하는 정사각형 중 가장 큰 정사각형의 변의 길이
i가 행, j가 열임에 유의하자. (xy좌표계와 순서가 반대)

dist[i][j]는 이전의 값으로 다음과 같이 구할 수 있다.

주어진 입력을 확장시켜 다음과 같은 행렬을 구성해보자
```
0 1 0 0 0
0 1 1 1 1
0 1 1 1 0
1 1 1 1 0
0 0 0 1 0
```

길이가 2인 정사각형(2, 2)에서 3인 정사각형(3, 3)으로 확장하기 위해서는 아래의 한 행과 오른쪽의 한 열 모두 1로 구성되어있어야 하고 해당 지점(3, 3)의 값이 1이어야 한다.

0 . 0 0 0   0 . 0 0 0   0 . 0 0 0   0 . 0 0 0   0 . 0 0 0
0 1 1 1 .   0 1 1 . .   0 . . 1 .   0 . . . .   0 . . . .
0 1 1 1 0 = 0 1 1 . 0 + 0 . . 1 0 + 0 . . . 0 + 0 . . . 0
. 1 1 1 0   . . . . 0   . . . . 0   . 1 1 . 0   . . . 1 0
0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0

이는 다음과 같이 세 정사각형의 구성으로도 볼 수도 있다.
```
0 . 0 0 0   0 . 0 0 0   0 . 0 0 0   0 . 0 0 0   0 . 0 0 0
0 1 1 1 .   0 1 1 . .   0 . 1 1 .   0 . . . .   0 . . . .
0 1 1 1 0 = 0 1 1 . 0 + 0 . 1 1 0 + 0 1 1 . 0 + 0 . . . 0
. 1 1 1 0   . . . . 0   . . . . 0   . 1 1 . 0   . . . 1 0
0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0
```
- (3, 3)까지의 사각형은 (2, 2), (2, 3), (3, 2)까지의 사각형과 (3, 3)지점 자체로 구성되어있다.
- (2, 2), (2, 3), (3, 2) 모두 길이가 2인 정사각형이 가장 큰 정사각형이고, 현재 지점도 1로 정사각형을 확장할 수 있으므로 사각형을 확장할 수 있고 dist[3][3]의 값은 3이 된다.
위의 경우는 (3, 3)을 구성하는 사각형들의 길이가 모두 같아서 파악이 쉽지만 그렇지 않은 경우에 대해서도 생각해보자. 예를 들어 (2, 2)가 길이가 3인 정사각형을 포함한다고 가정해보자.
```
1 1 1 0 0   1 1 1 0 0   . . . 0 0   . . . 0 0   . . . 0 0
1 1 1 1 .   1 1 1 . .   . . . 1 .   . . . . .   . . . . .
1 1 1 1 0 = 1 1 1 . 0 + . . . 1 0 + . . . . 0 + . . . . 0
. 1 1 1 0   . . . . 0   . . . . 0   1 1 1 . 0   . . . 1 0
0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0
```
```
1 1 1 0 0   1 1 1 0 0   . . . 0 0   . . . 0 0   . . . 0 0
1 1 1 1 .   1 1 1 . .   . . 1 1 .   1 1 1 . .   . . . . .
1 1 1 1 0 = 1 1 1 . 0 + . . 1 1 0 + 1 1 1 . 0 + . . . . 0
. 1 1 1 0   . . . . 0   . . . . 0   1 1 1 . 0   . . . 1 0
0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0   0 0 0 . 0
```
- 이 경우, 행은 확장할 수 있지만 (0, 3)의 값이 0이어서 우측 열을 확장할 수 없어 길이가 4인 정사각형으로 확장할 수 없다.
- 정사각형의 관점에서 보면 (2, 2)과 (3, 2)의 정사각형은 모두 길이가 3이지만, (2, 3)의 정사각형의 길이가 2이다.
- 즉 (3, 3)까지의 정사각형은 (2, 3)의 정사각형 때문에 한 변의 길이가 3인 정사각형까지만 확장될 수 있다.
- 이는 처음에 선택한 지점이 (2, 2), (2, 3), (3, 2)든 상관없이 모두 동일하게 적용된다.
남은 한 조건인 (3, 3) 지점의 값은 경우가 간단하다.
```
0 . 0 0 0
0 1 1 1 .
0 1 1 1 0
. 1 1 0 0
0 0 0 . 0
```
- 해당 지점의 값이 0이면 그 값을 꼭지점으로는 어떤 정사각형도 만들지 못하므로 dist[3][3]의 값은 0이 된다.
- 심지어 길이가 1인 정사각형도 만들지 못한다.
이 조건을 정리하면 다음과 같이 일반화 할 수 있다. dist[i][j] 값을 구할 때,
- matrix[i][j]의 값이 0이면 그 값은 0이 된다.
- matrix[i][j]의 값이 0이 아니면 dist[i][j]를 구성하는 dist[i - 1][j], dist[i][j - 1],dist[i - 1][j - 1]의 값 중 최솟값에 1을 더한 값이 된다.

점화식으로 정리하면 다음과 같다.

if (matrix[i][j]) {
    dist[i][j] = Math.min(dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1]) + 1;
}

디버그

처음에는 왼쪽 상단을 기준점으로 잡고 인접 사각형을 확인해 모두 1로 구성되어있어서 사각형을 만들 수 있으면 값을 1로, 아니면 0을 반환하고 반환 값을 이용해 한 칸 더 큰 정사각형을 만들 수 있는지를 확인했었는데, 이 방식으로는 사각형의 길이가 1인 케이스를 포함하지 못해서 틀렸었다.

// !틀린 풀이입니다.
function main() {
    const d = Math.min(N, M);
    // 초기값을 1로 잡으면 답이 0인 경우를,
    // 0으로 잡으면 답이 1인 경우를 포함하지 못한다.
    let area = 1;
    for (let k = 1; k < d; k += 1) {
        for (let i = 0; i < N - k; i += 1) {
            for (let j = 0; j < M - k; j += 1) {
                if (!matrix[i][j] || !matrix[i + 1][j] || !matrix[i][j + 1] || !matrix[i + 1][j + 1]) {
                    matrix[i][j] = 0;
                    continue;
                }
                matrix[i][j] = 1;
                area = (k + 1) * (k + 1);
            }
        }
    }
    return area;
}

dist를 구할 때 (1, 1)부터 탐색을 시작했는데 max를 구하는 과정이 중간에 있으면 다음과 같은 경우에 첫 행과 첫 열의 1을 인식하지 못해 답을 0으로 구하게 된다.
```
1 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
```
- 이 경우 풀이와 같이 마지막에 (0, 0)부터 전체를 순회하면서 max를 다시 구해주거나
- 다음과 같이 첫 행과 첫 열을 별개의 경우로 처리해주어야 한다.
```
if (i === 0) max = Math.max(max, dist[i][j]);
else if (j === 0) max = Math.max(max, dist[i][j]);
```