[LeetCode] 835. Image Overlap

문제 요약

0과 1로 이루어진 n x n 이미지 img1, img2가 주어진다.
img1을 상하좌우로 평행이동(회전 X)시켜 img2 위에 겹쳤을 때, 두 이미지 모두 1인 칸의 최대 개수를 구한다.
이미지 밖으로 밀려난 칸은 버린다.

• 1 <= n <= 30

핵심 아이디어

가능한 모든 평행이동을 다 시도해 보는 완전탐색이다.

• 행 이동량 dr, 열 이동량 dc는 각각 -(n-1) ~ n-1 범위이다.
• 따라서 이동 조합은 (2n-1)²개이다.
• 각 이동마다 img2[r][c]와 img1[r + dr][c + dc]를 비교해서 둘 다 1인 칸을 센다.
• 범위를 벗어난 좌표는 겹치지 않는 영역이므로 건너뛴다.

n이 최대 30이라 O(n⁴) ≈ 약 290만 번 연산으로 충분히 통과한다.

처음에 틀렸던 부분

1. 이동량을 n²개로만 잡았다

const rowWeight = Math.floor(i / squareN); // 항상 0
const colWeight = i % squareN;

n * n으로 나누는 바람에 행 이동이 한 번도 일어나지 않았다.
게다가 이동량은 음수 방향까지 있어서 경우의 수가 n²이 아니라 (2n-1)²이다.

2. 한쪽 방향으로만 이동했다

이동량을 0 이상으로만 두면 img1을 왼쪽·위로 당기는 경우만 확인하게 된다.
오른쪽·아래 이동도 봐야 하므로 이동량 범위를 -(n-1)부터 시작해야 한다.

3. 0끼리 겹친 것도 셌다

if (img1[...][...] === img2[j][k]) overlap++;

이렇게 쓰면 0 === 0도 카운트된다.
문제에서 세는 것은 둘 다 1인 칸뿐이다.

풀이 코드

function largestOverlap(img1: number[][], img2: number[][]): number {
    const n = img1.length;
    let maxOverlap = 0;

    for (let dr = -(n - 1); dr < n; dr++) {
        for (let dc = -(n - 1); dc < n; dc++) {
            let overlap = 0;
            for (let r = 0; r < n; r++) {
                const tr = r + dr;
                if (tr < 0 || tr >= n) continue;
                for (let c = 0; c < n; c++) {
                    const tc = c + dc;
                    if (tc < 0 || tc >= n) continue;
                    if (img1[tr][tc] === img2[r][c] && img2[r][c] === 1) overlap++;
                }
            }
            maxOverlap = Math.max(maxOverlap, overlap);
        }
    }

    return maxOverlap;
};

행 범위 검사를 바깥 루프에서 먼저 하면, 범위를 벗어난 행은 안쪽 열 루프를 아예 돌지 않는다.

복잡도

• 시간: O(n⁴), 이동 조합 (2n-1)² x 칸 수 n²
• 공간: O(1)

더 나아가기: 1의 좌표만 비교하기

1인 칸의 좌표만 모아 두고, img1의 1 좌표 - img2의 1 좌표 차이 벡터를 Map으로 센다.
같은 차이 벡터가 나온 횟수는 곧 그만큼 이동했을 때 겹치는 1의 개수이므로, 가장 많이 나온 값이 답이 된다.
이미지에 1이 적을수록 완전탐색보다 빠르다.

정리

• 평행이동 문제는 이동량 범위가 음수까지인지 먼저 확인한다.
• "겹친다"의 정의(값이 같은 것인지, 둘 다 1인 것인지)를 정확히 읽는다.
• 제약이 작으면(n <= 30) 완전탐색부터 떠올려도 된다.