C++로 전구 하나로 비출 수 있는 최대 셀 개수 구하기

문제 소개

h × w 크기의 격자가 주어졌다고 가정해 보겠습니다. 격자의 각 칸에는 전구 또는 장애물이 있을 수 있습니다. 전구가 놓인 칸은 왼쪽, 오른쪽, 위, 아래 네 방향의 칸을 밝히며, 빛은 장애물에 가로막히지 않는 한 계속 퍼져 나갑니다. 장애물이 있는 칸은 빛을 받을 수 없으며, 전구의 빛이 다른 칸에 도달하는 것을 차단합니다.

격자는 문자열 배열 형태로 주어지며, '#'은 장애물을, '.'은 빈 칸을 나타냅니다. 전구는 단 하나만 사용할 수 있고, 이를 가장 유리한 위치에 배치했을 때 비출 수 있는 칸의 최대 개수를 구하는 것이 이 문제의 목표입니다.

입출력 예시

예를 들어 h = 4, w = 4이고 grid = {"#...", "....", "...#", "...."}가 입력으로 주어지면, 결과는 7이 됩니다.

C++로 전구 하나로 비출 수 있는 최대 셀 개수 구하기

위 그림을 통해 격자에서 실제로 빛이 닿는 칸들을 확인할 수 있습니다.

풀이 접근 방식

이 문제의 핵심 아이디어는 간단합니다. 어떤 칸에 전구를 놓으면, 그 칸이 속한 가로 방향의 연속된 빈 칸 구간과 세로 방향의 연속된 빈 칸 구간에 있는 나머지 칸들이 모두 밝아집니다. 여기서 '연속 구간'이란 장애물('#') 사이에 끼어 있는 빈 칸('.')들의 묶음을 뜻합니다.

따라서 각 칸에 대해 (가로로 비출 수 있는 칸 수)와 (세로로 비출 수 있는 칸 수)를 미리 계산해 두고, 두 값의 합이 최대가 되는 칸을 찾으면 됩니다. 최종 답에 1을 더하는 이유는 전구 자체가 놓인 칸 역시 밝혀지는 칸에 포함되기 때문입니다.

알고리즘 단계

first 배열(가로 방향) 계산: 각 행을 왼쪽에서 오른쪽으로 스캔하며, 장애물을 만나면 카운트를 0으로 초기화하고, 빈 칸을 만나면 현재 구간 내 앞쪽 빈 칸 수를 first[i][j]에 기록한 뒤 카운트를 증가시킵니다.
이어서 같은 행을 오른쪽에서 왼쪽으로 다시 스캔하면서 지금까지 확인한 first 값의 최댓값을 각 칸에 덮어씁니다. 그러면 first[i][j]에는 해당 칸의 가로 연속 구간에서 자기 자신을 제외한 칸 수가 저장됩니다.
second 배열(세로 방향) 계산: 동일한 방식을 열 단위로 적용해, 위→아래 스캔 후 아래→위 스캔으로 각 칸에서 세로 방향으로 비출 수 있는 칸 수를 구합니다.
정답 도출: 모든 칸을 순회하며 first[i][j] + second[i][j]의 최댓값을 찾고, 여기에 1을 더해 반환합니다.

C++ 구현 코드

아래 구현을 참고하면 이해에 도움이 됩니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<string> grid){
    vector<vector<int>> first(h, vector<int>(w));
    for(int i = 0; i < h; i++) {
        int count = 0;
        for(int j = 0; j < w; j++) {
            if(grid[i][j] == '#') {
                count = 0;
                continue;
            } else {
                first[i][j] = count;
                count++;
            }
        }
        int k = 0;
        for(int j = w-1; j >= 0; j--) {
            if(grid[i][j] == '#') {
                k = 0;
                continue;
            } else {
                k = max(k, first[i][j]);
                first[i][j] = k;
            }
        }
    }
    vector<vector<int>> second(h, vector<int>(w));
    for(int j = 0; j < w; j++) {
        int count = 0;
        for(int i = 0; i < h; i++) {
            if(grid[i][j] == '#') {
                count = 0;
                continue;
            } else {
                second[i][j] = count;
                count++;
            }
        }
        int k = 0;
        for(int i = h-1; i >= 0; i--) {
            if(grid[i][j] == '#') {
                k = 0;
                continue;
            } else {
                k = max(k, second[i][j]);
                second[i][j] = k;
            }
        }
    }
    int result = 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            result = max(result, first[i][j] + second[i][j]);
        }
    }
    return result + 1;
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"#...", "....", "...#", "...."};
    cout << solve(h, w, grid);
    return 0;
}

입력

4, 4, {"#...", "....", "...#", "...."}

출력

복잡도 분석

격자의 모든 칸을 몇 번의 선형 스캔만으로 처리하므로 시간 복잡도는 O(h × w)입니다. 두 개의 2차원 배열을 추가로 사용하므로 공간 복잡도 역시 O(h × w)입니다.