[PS] BOJ 20543번 폭탄 던지는 태영이

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

(혹시나 풀어보실 분들은 알고리즘 분류를 보지 않고 풀어보길 권장합니다.)

이 문제를 처음 보고, 간만에 신선하다는 느낌을 받았다.

어떤 알고리즘이나 자료구조를 알고 있으면, 

흔히 많이 나오는 유형에 속하는 문제가 있는가 하면, 그렇지 않은 문제도 있다.

이 문제를 풀면서 규칙을 찾고 시간을 단축시켜 나가는 과정이 재미있었고,

예전에 수학에 매력을 느꼈을 때의 느낌과 비슷했다.

물론, 영문까지 포함한 많은 문제를 풀어본 건 아니지만 부족한 내가 느끼기에는 그랬다.

어려운 자료구조를 쓰지 않아도 (기본적인 재료로도) 

충분히 난이도를 높여 갈 수 있는 (까다로우며 맛있는 요리?) 그런 문제들의 초입에 해당하지 않나 싶다.

아래는 풀이를 생각한 순서이다.

1. 출력은 맞지만 시간초과 풀이

2. 정답 풀이

먼저, 제한도 까다롭지 않고 시간도 2초나 주어졌기 때문에 풀어보는 것이 중요하다고 생각했다.

N이 2,000일 때, 2차원 배열의 데이터 개수는 2,000 x 2,000 = 4,000,000 이다.

O(n)에 해당하는 과정은 시간초과를 발생시키지 않으나, 폭탄을 찾기 위해서

자기 자신의 위치(arr[i][j])에서 가능한 모든 경우의 수를 찾으려고 하면 시간초과가 뜰 것이다.

여기까지 생각하고, 규칙을 생각해보았다.

예제 입력과 예제 출력들을 보면서, 가장 외곽에 위치한 배열의 원소들부터 채워가면 될 것이라고 생각했다.

먼저, (0, 0)부터 시작한다고 하면, 시계방향으로 테두리를 돌면서 1칸씩 안쪽으로 진행해볼 수 있다.

그러나 가장 첫 줄을 시물레이션 해보면, 

우리가 이중 for문을 통해 배열을 탐색하는 일반적인 과정으로도 채워나갈 수 있다는 것을 알게 되었다.

왜냐하면, 폭탄이 있을 수 없는 구역이 존재하기 때문이다. (m = 1의 경우는 예외)

m이 1인 경우에는 그대로 절댓값으로 바꿔서 출력하면 되고,

m이 3이상의 홀수인 경우에 생각해보면, 외곽 테두리에 폭탄이 존재할 수 없는 구역이 

m / 2 에 해당하는 줄 수만큼인 것을 알 수 있었다.

이런 방식으로 처음부터 하나씩 폭탄을 탐색할 때, 

검사하고자 하는 위치 (y, x) 의 m / 2 만큼 떨어진 (y + m / 2, x + m / 2)의 위치에 폭탄 숫자를 갱신하게 된다.

여기까지 생각했을 때, 제출한 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

void checkBomb(vector<vector<int>> &arr, vector<vector<int>> &ret, int y, int x, int r)
{
    int n = arr.size();
    int nowCell = abs(arr[y][x]);
    int gy = -1, gx = -1;
    int retSum = 0;
    for (int i = y - r; i <= y + r; ++i)
    {
        for (int j = x - r; j <= x + r; ++j)
        {
            if (i < 0 || j < 0 || i >= n || j >= n) continue;
            if (ret[i][j] == -1) { gy = i; gx = j; }
            else retSum += ret[i][j];
        }
    }

    if (gy != -1) ret[gy][gx] = nowCell - retSum;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(n)), ret(n, vector<int>(n, -1));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> arr[i][j];

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (i < m / 2 || j < m / 2 || n - i - 1 < m / 2 || n - j - 1 < m / 2) ret[i][j] = 0;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            checkBomb(arr, ret, i, j, m / 2);
            cout << ret[i][j] << ' ';
        }
        cout << '\n';
    }
}

위의 코드로 예제는 모두 맞았고, 제출하였을 때 시간초과가 발생했다.

이윽고, checkBomb 함수에서 배열에 존재하는 값을 중복해서 더해주는 부분을 

누적합(Prefix Sum : 부분 연속 구간을 더한 값을 미리 저장해두고 불러와 사용하기) 기법을 통해 줄일 수 있음을 깨달았다.

이제 정답으로 가는 방법은 알았으나, 구현하는데 있어서 디테일한 부분이 신경쓰였고 꽤 시간을 투자하게 되었다.

1. 누적합 배열을 하나씩 갱신해나가기 (추가적으로, 예외 처리 + 중복되는 부분 계산)

2. 문제의 제한 범위가 int 내에 있지만, 계산하는 과정에서 오버플로우 발생 유무

이 두 가지에 대한 디버깅을 끝내고, 마침내 정답을 받을 수 있었다.

http://boj.kr/cdf75dc65ae34dd1bc5a6d0bf37a5a28