[Algorithm] 백준 17114 하이퍼토마토 - 구데기같지 않은 풀이 (C++)

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

구데기컵에 출제된 문제입니다. 구데기같이 11중 반복문과 BFS를 통해서 풀 수 있습니다. (물론 그게 아주 정상적인 방법입니다.)

하지만 차원 확장에 대해 조금 더 생각해보면 규칙을 발견할 수 있고, 11차원 뿐만 아니라 자연수 n에 대해 일반적으로 답을 낼 수 있습니다.  코드도 아주 짧아져서 숏코딩에 도전할 수도 있죠. 이 글에서는 제가 며칠 동안 삽질하면서 발견한 꽤 아름다운(?) 풀이를 설명하려 합니다. 관련 지식은 BFS만 알고 계시면 됩니다만, 꽤 인내심이 필요할 것 같습니다. 제가 부족한 탓에 쉽게 설명을 못하겠더라구요.

 

1. 토마토 배열을 일차원으로 표현

2차원(평면)은 1차원(선)을 모아놓은 것이고, 3차원은 2차원을 모아놓은 것입니다. 즉 n차원은 n-1차원의 집합이며, 재귀적으로 돌고 돌아 n차원은 결국 1차원을 모아놓은 형태로 표현 가능합니다.

3차원 공간의 단순한 예로 생각해봅시다. 3×3×4 크기의 토마토 창고 tomatoes (int[4][3][3])가 있다고 합시다. 바닥에 2×3 크기의 2차원 창고와, 그게 4개 쌓인 3차원의 모습을 머리속에서 그려볼 수 있을 것입니다. 그리고 모든 칸에 토마토가 있으며 (2, 2, 2) 위치에만 익은 토마토가 있다고 생각합시다. 그러면 다음과 같은 모양이 되겠죠.

1층          2층         3층          4층
{0, 0, 0}   {0, 0, 0}   {0, 0, 0}   {0, 0, 0}
{0, 0, 0}   {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}}, // 1층
{{0, 0, 0},{0, 1, 0},{0, 0, 0}}, // 2층
{{0, 0, 0},{0, 0, 0},{0, 0, 0}}, // 3층
{{0, 0, 0},{0, 0, 0},{0, 0, 0}}  // 4층

1층 - 2층 - 3층 - 4층 순으로 옆으로 나열하면 일차원 배열 형태로 만들 수 있습니다.

 

2. 인접한 토마토에 접근

일반적으로는 토마토 문제를 풀 때 인접한 토마토에 접근하기 위해 다음과 같은 배열을 선언해줍니다. 델타 배열이라고 부르더군요.

int dX[6] = {1, -1, 0, 0, 0, 0};
int dY[6] = {0, 0, 1, -1, 0, 0};
int dZ[6] = {0, 0, 0, 0, 1, -1};

X, Y, Z축으로 좌표에 각각 ±1을 취했을 때 인접하다고 보며, 이와 같이 코드를 짜면 반복문에서 (x + dX[i], y + dY[i], z + dZ[i])와 같이 탐색해야 할 좌표에 쉽게 접근할 수 있습니다.

구데기같은(사실은 지극히 정상적이고 일반적인) 방식으로 문제를 푼다면 크기 22인 방향배열 11개를 직접 선언해 주어야 하며, n차원일 경우에 2n개의 방향배열을 n개 선언해 주어야 합니다.

하지만 일차원 배열로 접근할 때 코드는 아주 단순해집니다.

3×3×3의 배열을 예로 한 번 들어봅시다. 각 칸을 인덱스로 표현하면 다음 그림과 같은 상태가 됩니다. 빨간 부분이 토마토가 익은 부분, 파란 부분은 그 인접한 칸을 의미합니다.

먼저 x축을 보면 당연하게도 파란색(인접한) 값(인덱스)은 빨간색 값에 ±1을 취한 값들입니다. 그리고 y축을 보면 파란색 값은 빨간색 값에 ±3을 한 값입니다. z축을 봅시다. ±9를 취한 값이군요. 뭔가 일반화를 할 수 있을 것 같은 냄새가 풀풀 풍기지 않나요?

일반화가 될 지 좀 더 확신을 가지기 위해 4×3×3 tomatoes 배열의 (3, 2, 2), 즉 tomatoes[1][1][2]에 익은 토마토가 있는 경우를 생각해 봅시다.

곰곰이 생각해보면, x축으로 인접한 원소와의 인덱스 차이는 1, y축에서 차이는 4, z축에서 차이는 12임을 알 수 있습니다. 첫번째 x축은 항상 1, 그 다음 y축은 x축의 크기만큼, z축은 x축의 크기와 y축의 크기를 곱한 만큼(=xy평면의 넓이)의 차이가 발생하는 것입니다.

다시 말해서,  x축으로 탐색할 때는 항상 1, y축으로 탐색할 때 1차원 공간의 크기는 x축(1차원)의 크기, z축으로 탐색할 때는 xy평면(2차원)의 크기, 그 다음 w축으로 탐색할 때는 xyz공간(3차원)의 크기, ... 이런식으로 확장되며 인덱스 차이를 정의할 수 있습니다. 즉 기하학적으로는 탐색하는 축의 인덱스 k에 대해 'k차원 공간의 누적 크기'가 곧 그 인덱스 차이인 것이죠. (여기서 0차원 공간의 크기는 1이라고 제가 임의로 정의했습니다.)

n차원은 n-1차원을 모아놓은 집합이라는 것을 생각하면 다음과 같은 일반식을 찾아낼 수 있습니다.

탐색하는 축의 인덱스 k와 그 축의 크기 s[k]에 대해서 임의의 토마토와 k번째 축으로 인접하는 토마토의 인덱스 차이 dist[k]는
dist[0] = 1로 정의,
dist[k] = $\prod_{i=0}^{k-1} s[i]$ = s[0] × s[1] × ... × s[k-1] (단, k≥1)
∴ dist[k] = dist[k-1] * s[k-1]

그래서 이 dist 배열을 만들면 차원의 수를 크기로 가지는 1차원 배열 하나로 인접한 배열에 접근할 방법이 생깁니다. 즉 델타 배열 하나 것이죠. 위에서 예를 든 4×3×3 tomatoes의 경우에 dist배열 {1, 4, 12}를 생성하고, 이 배열 내 임의의 좌표 𝑥(0 ≤ 𝑥 < 4×3×3)에 익은 토마토가 있다면 𝑥±1, 𝑥±4, 𝑥±12 의 총 6개 좌표들을 탐색하여 BFS를 수행하면 된답니다.

 

3. 인접 인덱스의 유효성 검사

너비우선탐색을 수행할 때, 당연하게도 dist를 통해서 얻은 "인접한 인덱스"가 토마토 배열의 범위 [0, 크기) 를 벗어나는 경우는 탐색 과정에서 무시해야 합니다. 그런데 dist를 통해 얻은 인덱스가 범위를 벗어나지 않아도 무시해야 하는 경우가 있습니다. 아마 위의 과정에서 여러 차원을 그려보면서 이미 알아차린 사람도 있겠지만, 다음과 같은 3×2×2 배열을 보면 그러한 사례를 찾을 수 있습니다.

보라색으로 표시한 부분은 dist를 통해서 얻은 "인접한 칸"이지만, 사실은 인접하지 않다는 것을 알 수 있습니다. 이 외에도 간단하게 2차원에서 생각해보아도 이런 사례들을 찾을 수 있습니다. 이러한 부분을 무시해주어야 하는데, 파란색과 보라색의 차이를 자세히 탐구해보면 알 수 있습니다.

8에서 왼쪽(x축의 음의 방향)으로 탐색했을 때 7은 왼쪽에 있고, 오른쪽(x축의 양의 방향)으로 탐색했을 때 8은 왼쪽으로 갔죠. 탐색하는 방향과, 토마토에서 토마토로 가는 방향이 일치해야 인접해 있다고 말할 수 있는 것입니다.

위에서 다룬 dist[k]의 기하학적인 의미를 생각해보면서 그림을 USIM히 들여다 보면 탐색하는 k번째 축에 대해서 어떤 인덱스가, (k+1)차원 공간에서 몇번째 위치를 점유하고 있는지를 통해 그 유효성을 검사할 수 있다는 것을 짐작할 수 있습니다. 이 말만으로는 이해가 어려우니 예를 들어봅시다.

6, 7, 8은 1차원 공간에서 0, 1, 2번째를 점유하고 있고, 9, 10, 11도 0, 1, 2번째를 점유하고 있습니다. 각각의 점유하는 위치는, 해당 인덱스를 3(=1차원 공간의 크기)으로 나눈 나머지이죠. 8은 2번째를 점유하고 있고 x축 양의 방향으로 탐색한 9가 0번째를 점유하고 있습니다. 인덱스 값이 증가했으나 점유한 위치값은 감소했죠. 

또, 0~5와 6~11은 1번째 차원(x, y축)에서 0~5번째를 점유하고 있습니다. 이번에는 점유 위치는 인덱스를 6(=2차원 공간의 크기)으로 나눈 나머지입니다. 8에서 5를 탐색하는 경우도 인덱스는 감소했으나 점유 위치값은 증가하여, 인덱스와 점유 위치 값의 증감 여부가 다르기 때문에 유효하지 않습니다.

이제 이를 좀 더 정형화된 방식으로 표현해 봅시다. 익은 토마토의 인덱스를 lastIndex, dist배열을 통해 얻은 "인접한 칸"의 좌표를 newIndex로 표현하겠습니다. lmod, nmod는 lastIndex와 newIndex 각각이 탐색하는 축 k에 대해 (k+1)차원 공간에서 점유하는 위치값입니다.

lmod = lastIndex % dist[k+1];
nmod = newIndex % dist[k+1];

 

last → new로 탐색할 때 인덱스가 커지면 mod값도 커져야 하며 인덱스가 작아지면 mod값도 작아져야 합니다. 즉 lastIndex < newIndex 이면 lmod < nmod 이어야 하고, lastIndex > newIndex 이면 lmod > nmod 이어야 합니다.

x축으로 9를 탐색할 때, 인덱스는 증가했지만 mod값은 감소했기 때문에 유효하지 않고, y축으로 5를 탐색할 때 인덱스는 감소했지만 mod값은 증가했기 때문에 유효하지 않은 것이죠.

위의 Bold처리 된 두 개의 유효 조건은 간단하게 (newIndex-lastIndex) * (nmod-lmod) > 0 로 짧게 표현할 수 있습니다.

 

4. 코드

#include <iostream>
#include <queue>
#define F(i, e) for (int i = 0; i < e; ++i)

using namespace std;

struct Tomato
{
    int index = 0, state = 0, days = 0;
};

int main()
{
    int ripped = 0, empty = 0, total = 1, days = 0, s[11], dist[11] = {1};

    F(i, 11)
    {
        cin >> s[i];
        total *= s[i];
    }

    F(i, 11) if(i) dist[i] = s[i - 1] * dist[i - 1];

    Tomato tomatoes[total];
    queue<Tomato> q;

    F(i, total)
    {
        cin >> tomatoes[i].state;
        tomatoes[i].index = i;
        
        if (tomatoes[i].state > 0) q.push(tomatoes[i]);
        else if (tomatoes[i].state < 0) empty++;
    }

    while (!q.empty())
    {
        Tomato f = q.front(); q.pop();
        ripped++;
        days = f.days;

        F(i, 22)
        {
            int k = i / 2,
                sign = 1 - 2 * (i % 2),
                nextIndex = f.index + sign * dist[k],
                dimSize = dist[k] * s[k],
                lmod = f.index % dimSize,
                nmod = nextIndex % dimSize;

            if (nextIndex >= 0 && nextIndex < total
            &&  sign * (nmod - lmod) > 0
            &&  !tomatoes[nextIndex].state)
            {
                tomatoes[nextIndex] = {nextIndex, 1, f.days + 1};
                q.push(tomatoes[nextIndex]);
            }
        }
    }
    
    if (ripped + empty - total || ripped <= 0) days = -1;
    cout << days;

    return 0;
}