[백준] 하이퍼 토마토

5 분 소요

문제

출처

이해

입력

첫 번째 행에 11차원 창고의 크기가 주어진다.
그 뒤로 nopqrstuvw행 m열로 창고의 상태가 주어진다.
m, n, o, p, q, r, s, t, u, v, w (창고 크기)
- 타입: 자연수
창고의 상태
- 타입: 문자열 (11차원 배열)
- 크기: m, n, o, p, q, r, s, t, u, v, w
- 최종 원소: -1, 0, 1
  - -1: 빈 칸
  - 0: 안 익은 토마토
  - 1: 익은 토마토

출력

토마토가 모두 익을 때까지 걸리는 최소 일 수

조건

창고는 11차원 격자 공간이며, 각 칸에 하나의 토마토만 담을 수 있다.
창고의 크기는 다음을 만족해야 한다.
- 1 <= m*n*o*p*q*r*s*t*u*v*w <= 10^6
익은 토마토가 담긴 칸에 인접한 격자의 토마토는 다음 날 익는다.
- 칸 A에 인접한 칸은 칸 A에서 맨해튼 거리로 1만큼 떨어진 모든 칸을 말한다.
토마토는 혼자서 익지 않는다.
시작 시점에 이미 모든 토마토가 익어있는 상태면 0을 출력한다.
시간이 아무리 흘러도 모든 토마토가 익을 수 없다면 -1을 출력한다.

예시

입력
6 4 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력
8

접근

사실 문제 자체는 전형적인(?) 토마토 문제이다. 2차원 토마토, 3차원 토마토에 이어서 11차원 토마토가 되었을 뿐이다. 이런 종류의 문제는 BFS로 쉽게 해결할 수 있다. 다만 2차원, 3차원 때와는 다르게 11차원 벡터를 사용해야 한다. 그리고 살펴봐야할 인접한 칸이 22개나 된다. 이를 하드코딩으로 구현할 수도 있으나 다른 방법을 사용해보자.

우선 가장 큰 문제는 차원이 너무 많다는 것이다. 쉽게 해결하려면 추상화가 필요하다. 추상화하는 방법은 n차원 배열을 나타내는 클래스를 정의하는 방법도 있고, 11차원 배열을 1차원 배열로 평탄화(flatten)하는 방법도 있다.

각각 장단점이 있는데, 전자의 경우 직관적인 좌표 이동이 가능하지만, 클래스를 정의할 때 복잡한 template meta programming을 해야 하고, 후자의 경우 특별한 자료구조가 필요 없지만 공간의 상태를 확인하고 탐색하는 데에 추가적인 연산이 필요하다는 단점이 있다.

여기서는 후자를 구현해볼 것이다. 11차원 배열을 1차원 배열로 만든다는 것은 11차원 배열의 원소에 순서를 부여하여 일렬로 줄을 세우는 것과 같다. 순서는 의외로 쉽게 정의할 수 있는데, 고차원 좌표부터 비교해서 좌표가 작은 쪽에 높은 우선순위를 주는 것이다.

예를 들어보자. 

(1, 0, 0)은 (0, 100, 0)보다 우선순위가 높다.
3차원에서는 서로 동일하지만 2차원에서 앞서기 때문이다.

(0, 0, 1)은 (1, 0, 1)보다 우선순위가 높다.
3차원 2차원에서는 서로 동일하지만 1차원에서 앞서기 때문이다.

이런 방식으로 우선순위를 정의할 때 순위가 중복되지 않으려면 n차원에서 1만큼 증가할 때, 최소한 n-1차원 배열의 원소의 수만큼 건너뛰어야 한다.

예를 들어, 2차원 배열 2 * 3을 생각해보자.

0, 1, 2
3, 4, 5

1행 1열 원소와 2행 1열 원소의 우선순위의 차이는 1차원 배열의 크기인 3 이상이어야 함을 알 수 있다.

또한 이로부터 알 수 있는 사실은 n-1차원에서 얼마가 바뀌든, n차원에서 1만큼 바뀔 때 더 큰 차이가 발생한다는 것이다. 그러므로 $(p_1, p_2,\dots, p_n)$를 좌표로 가지는 칸의 우선순위는, $D_i$를 i차원 배열의 원소의 수라고 할 때, 다음과 같이 계산할 수 있다.

\[\text{order}((p_1, p_2,\dots, p_n)) = \sum_{i = 1}^{n} D_{i-1}p_i\]

참고로 0차원 배열은 스칼라(=점)이기 때문에 원소의 수는 1개이다.

다시 본론으로 돌아와서, 문제를 살펴보면 익은 토마토에 인접한 토마토는 다음날 반드시 익는다. 그러므로 같은 토마토를 여러번 볼 필요가 없다. 따라서 다음과 같은 pseudo code를 생각해볼 수 있다.

익어 있는 모든 토마토에 대하여, 인접 토마토를 익게 하고 날짜를 1일 증가시킨다.
새롭게 익은 토마토에 대하여, 인접 토마토를 익게 하고 날짜를 1일 증가시킨다.
새롭게 익은 토마토가 없다면 종료한다.
2로 돌아간다.

구현

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

const int N_DIM = 11;

using vi = vector<int>;
vi board;
vi dim = vi(N_DIM, 0);
vi dim_offset = vi(N_DIM, 0);
queue<int> q;

int to_be_matured;
int matured;

void print_vi(const vi& v, string msg="") {
    /*
        벡터 출력
    */
    if (msg.size())
        cout << msg << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

int pos_to_offset(const vi& pos) {
    /*
        11차원 좌표를 1차원 좌표로 바꿔서 return
    */
    int offset = 0;
    for (int i = 0; i < N_DIM; i++) {
        offset += dim_offset[i] * pos[i];
    }
    return offset;
}

void offset_to_pos(int offset, vi& pos) {
    /*
        1차원 좌표를 11차원 좌표로 바꿔서 return (pos에 할당)
    */
    for (int i = N_DIM - 1; i >= 0; i--) {
        pos[i] = offset / dim_offset[i];
        offset %= dim_offset[i];
    }
}

void trans_test() {
    /*
        좌표 변환 테스트
    */
    int offset = dim_offset[N_DIM - 1] * dim[N_DIM - 1] - 1;
    vi pos(N_DIM);
    
    cout << "> 기준 오프셋\n" << offset << endl;
    
    offset_to_pos(offset, pos);
    print_vi(pos, "> 좌표 변환");

    int new_offset = pos_to_offset(pos);
    cout << "> 복구한 오프셋\n" << new_offset << endl;
    cout << board[offset] << " == " << board[new_offset] << endl;
}

bool is_valid(const vi& pos) {
    /*
        주어진 좌표가 창고 내부이면 true
    */
    bool ret = true;
    for (int i = 0; i < N_DIM && ret; i++) {
        ret = ret && (0 <= pos[i] && pos[i] < dim[i]);
    }
    return ret;
}

void bfs() {
    /*
        토마토 익히기 시뮬레이션
        현재 상태에서 처리할 익어있는 토마토의 인접 토마토를 큐에 넣고 하루가 끝날 때마다 날짜를 음수로 넣는다.
    */
    int ans = 0;
    vi now(vi(N_DIM, 0)), nxt(vi(N_DIM, 0));
    while (!q.empty()) {
        int off = q.front(); q.pop();
        // cout << "토마토 방문: " << off << endl;
        if (off < 0) { // 오늘이 끝남
            ans = -off;
            if (!q.empty()) // 내일 처리할 토마토가 남아 있으면 날짜를 넣음.
                q.push(off-1);
            continue;
        }

        offset_to_pos(off, now);
        copy(now.begin(), now.end(), nxt.begin());
        for (int i = 0; i < N_DIM; i++) { // 차원 선택
            for (int j = 0; j < 2; j++) { // +, - 방향 선택
                nxt[i] = now[i] + 2 * j - 1;

                if (!is_valid(nxt))
                    continue;
                // print_vi(nxt, "유효한 칸");
                int nxt_off = pos_to_offset(nxt);
                if (board[nxt_off] == 0) {
                    // cout << "방문할 토마토: " << nxt_off << endl;
                    board[nxt_off] = 1;
                    matured++;
                    q.push(nxt_off);
                }
            }
            nxt[i] = now[i];
        }
    }
    
    cout << (to_be_matured == matured ? ans : 0) - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    for (int i = 0; i < N_DIM; i++) {
        cin >> dim[i];
        dim_offset[i] = i > 0 ? dim_offset[i-1] * dim[i-1] : 1;
    }
    // print_vi(dim, "[ 차원 크기 ]");
    // print_vi(dim_offset, "[ 차원 오프셋 ]");

    // 창고 상태를 입력 받으면서 익어 있는 토마토를 큐에 넣고 익지 않은 토마토의 개수를 센다. 
    // 앞서 정의한 순서대로 배열의 원소가 주어지므로 그냥 그대로 넣으면 됨.
    board.resize(dim_offset[N_DIM - 1] * dim[N_DIM - 1], 0);
    for (int i = 0; i < board.size(); i++) {
        cin >> board[i];
        if (board[i] == 1)
            q.push(i);
        else if (board[i] == 0)
            to_be_matured++;
    }
    q.push(-1);
    // print_vi(board, "[ 보드 ]");

    bfs();

    return 0;
}

Kuropow

[백준] 하이퍼 토마토

문제

이해

입력

출력

조건

예시

접근

구현

댓글남기기

참고

[백준] 마지막 팩토리얼 수2 - Python

[프로그래머스] 리틀 프렌즈 사천성

[프로그래머스] 디스크 컨트롤러

[프로그래머스] 오랜 기간 보호한 동물(2)