램프가 밝히는 모든 셀 개수의 합을 구하는 C++ 프로그램

문제 소개

H개의 행과 W개의 열로 이루어진 격자(grid)가 있다고 가정해 보겠습니다. 각 칸은 '깨끗한(tidy)' 상태이거나 '지저분한(untidy)' 상태이며, 깨끗한 칸 위에는 램프를 0개 이상 자유롭게 설치할 수 있습니다.

램프는 상·하·좌·우 네 방향으로 빛을 비춥니다. 빛은 격자의 가장자리에 도달하거나 지저분한 칸을 처음 만나기 직전까지 퍼져 나가며, 지저분한 칸 자체는 밝히지 못합니다. 물론 램프가 놓인 칸 스스로도 밝혀집니다. 격자에서 G[i, j]가 '.'이면 그 칸은 깨끗하고, '#'이면 지저분함을 의미합니다.

깨끗한 칸의 개수를 K라고 하면, 램프를 배치할 수 있는 방법은 총 2^K가지입니다. 이 모든 배치 각각에 대해 '하나 이상의 램프에 의해 밝혀지는 셀의 개수'를 계산하고, 그 값들을 모두 더한 결과를 10^9 + 7로 나눈 나머지를 구하는 것이 목표입니다.

예를 들어 다음과 같은 격자가 입력으로 주어진다면,

출력은 52가 됩니다.

풀이 접근 방법

2^K가지 배치를 일일이 시뮬레이션하면 시간이 너무 오래 걸리므로, 각 칸의 '기여도(contribution)'를 독립적으로 계산하는 방식으로 문제를 해결합니다. 핵심 아이디어는 다음과 같습니다.

• 각 깨끗한 칸 (i, j)에 대해, 그 칸을 밝힐 수 있는 후보 위치의 개수 src를 구합니다. 이는 (i, j)가 속한 가로 구간의 길이와 세로 구간의 길이를 더한 뒤 1을 빼면 되며, 네 방향으로 뻗을 수 있는 범위를 누적 계산하면 O(1)에 얻을 수 있습니다.
• (i, j)가 밝혀지려면 src개의 후보 위치 중 최소 한 곳에 램프가 있어야 합니다. 이를 만족하는 배치의 수는 (2^src − 1) × 2^(K − src)가지입니다.
• 따라서 정답은 모든 깨끗한 칸에 대한 (2^src − 1) × 2^(K − src)의 합을 10^9 + 7로 나눈 나머지와 같습니다.

이를 구현하기 위해 다음 단계를 따릅니다.

m := 10^9 + 7
N = 2003
u, l, r, d : N x N 크기의 2차원 배열, p : N^2 크기의 배열
h := 행의 개수, w := 열의 개수
tidy := 0 (깨끗한 칸의 개수)
p[0] := 1
for i := 1 to h * w:
    p[i] := p[i - 1] * 2 mod m   // 2의 거듭제곱 미리 계산

// 위쪽(u)과 왼쪽(l) 방향으로 뻗을 수 있는 범위 계산
for i := 0 to h - 1:
    for j := 0 to w - 1:
        u[i, j] := i
        l[i, j] := j
        if i > 0:
            u[i, j] := u[i - 1, j]
        if j > 0:
            l[i, j] := l[i, j - 1]
        if matrix[i, j] == '#':
            u[i, j] := i + 1
            l[i, j] := j + 1
        else:
            tidy 1 증가

// 아래쪽(d)과 오른쪽(r) 방향으로 뻗을 수 있는 범위 계산
for i := h - 1 down to 0:
    for j := w - 1 down to 0:
        d[i, j] := i
        r[i, j] := j
        if i < h - 1:
            d[i, j] := d[i + 1, j]
        if j < w - 1:
            r[i, j] := r[i, j + 1]
        if matrix[i, j] == '#':
            d[i, j] := i - 1
            r[i, j] := j - 1

// 각 칸의 기여도 합산
cnt := 0
for i := 0 to h - 1:
    for j := 0 to w - 1:
        if matrix[i, j] == '#':
            continue
        src := d[i, j] + r[i, j] - u[i, j] - l[i, j] + 1
        cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m
return cnt

C++ 구현 예시

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7, N = 2003;
int u[N][N], l[N][N], r[N][N], d[N][N], p[N * N];

int solve(vector<vector<char>> matrix){
    int h = matrix.size();
    int w = matrix[0].size();
    int tidy = 0;
    p[0] = 1;
    for (int i = 1; i <= h * w; ++i)
        p[i] = p[i - 1] * 2 % m;
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            u[i][j] = i;
            l[i][j] = j;
            if (i)
                u[i][j] = u[i - 1][j];
            if (j)
                l[i][j] = l[i][j - 1];
            if (matrix[i][j] == '#'){
                u[i][j] = i + 1;
                l[i][j] = j + 1;
            }
            else
                ++tidy;
        }
    }
    for (int i = h - 1; i >= 0; --i){
        for (int j = w - 1; j >= 0; --j){
            d[i][j] = i;
            r[i][j] = j;
            if (i < h - 1)
                d[i][j] = d[i + 1][j];
            if (j < w - 1)
                r[i][j] = r[i][j + 1];
            if (matrix[i][j] == '#'){
                d[i][j] = i - 1;
                r[i][j] = j - 1;
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            if (matrix[i][j] == '#')
                continue;
            int src = d[i][j] + r[i][j] - u[i][j] - l[i][j] + 1;
            cnt = (cnt + (p[src] - 1) * p[tidy - src]) % m;
        }
    }
    return cnt;
}
int main(){
    vector<vector<char>> matrix = { { '.', '.', '#' }, { '#', '.', '.' } };
    cout << solve(matrix) << endl;
}

입력 및 출력

main 함수에서는 다음과 같은 2행 3열 격자를 입력으로 사용합니다.

{ { '.', '.', '#' }, { '#', '.', '.' } }

이 프로그램을 실행하면 아래와 같은 결과가 출력됩니다.

52