백준 17114 '하이퍼 토마토'

• 이 풀이는 직전 포스트인 "백준 7569 '토마토'"의 풀이를 수정하는 것을 기준으로 서술하겠다. 같이 참고하면 좋다.
• 또한 7576번 (2차원 토마토), 7569번 (3차원 토마토)과 완전히 같은 논리로 11차원 배열과 11중 for문을 사용해서 문제를 풀 수도 있지만, 풀이 의의를 위해 임의의 차원 수에 대한 일반적인 코드를 짜기로 하였다.
  • 아래의 코드에서 DIM = 2로 고치면 7576번의 풀이가 되고, DIM = 3으로 고치면 7569번의 풀이가 된다. 이 풀이는 DIM = 11이므로 11차원인 '하이퍼 토마토'의 풀이가 된다.

아이디어

• 임의 차원(여기서는 11차원)에 대한 좌표를 다루는 것은 어렵기 때문에, 좌표를 1차원으로 평탄화(flatten)할 것이다.
  • 즉, 모양이 $m \times n \times \cdots \times w$인 11차원 배열을 크기가 $mn \cdots w$인 1차원 배열로 만들어 다룰 것이다.
  • 이하 일반적인 설명과 코드를 위해 $m = W_1, n = W_2, \cdots, w = W_{11}$ 등으로 쓰고, $W_0=1$이라 하고, $P_n = W_1W_2 \cdots W_n$이라 하자.
• 이때 1차원 배열의 크기는 $mn \cdots w = W_1W_2 \cdots W_{11} = P_{11}$임을 알 수 있다. 일반적으로 $\mathtt{dim}$ 차원을 평탄화 시킨 배열의 크기는 $P_\mathtt{dim}$임도 관찰할 수 있다.
• 그렇게 할 때, $i$차원 방향에 대한 변위 벡터 $dx_i$는 $\pm P_{i-1}$로 대응되는 것을 볼 수 있다. $(1 \le i \le \mathrm{dim})$
  • $dx_1 = (\pm1, 0, 0, \cdots, 0) \to \pm 1 + 0m + 0mn + \cdots + 0mnopqrstuv = \pm1$
  • $dx_2 = (0, \pm1, 0, \cdots, 0) \to \ \ \ 0 \pm 1m + 0mn + \cdots + 0mnopqrstuv = \pm m$
  • $dx_3 = (0, 0, \pm1, \cdots, 0) \to \ \ \ 0 + 0m \pm 1 mn + \cdots + 0mnopqrstuv = \pm mn$
  • $\cdots$
  • $dx_i \to \pm P_{i-1}$
• $nx_i = x_i + dx_i$의 범위 체크: $i+1$차원에 대한 인덱스가 달라지는지 확인하면 된다.
  • ($x_i$의 $i+1$차원에 대한 인덱스) = $\lfloor x_i / dx_{i+1} \rfloor \ \mathrm{mod} \ dx_{i+2} = \lfloor x_i / P_i \rfloor$
  • 구현할 때 음수 나눗셈에 주의한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static final int DIM = 11;
    static final int RIPEN = 1, UNRIPEN = 0, EMPTY = -1;

    static int ans;

    static int[] W = new int[DIM+1];
    static int[] P = new int[DIM+1];    // P[i] = W[1]*W[2]*...*W[i], P[DIM] = size
    static int[] map;
    static int cnt, tomato;

    static Queue<Integer> q = new ArrayDeque<>();
    static boolean[] enqueued;

    public static void main(String[] args) throws Exception {
        W[0] = 0;
        P[0] = 1;
        tk = new StringTokenizer(rd.readLine());
        for (int d=1; d<=DIM; d++) {
            W[d] = Integer.parseInt(tk.nextToken());
            P[d] = P[d-1] * W[d];
        }

        map = new int[P[DIM]];
        enqueued = new boolean[P[DIM]];

        for (int y=0; y<P[DIM]/W[1]; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<W[1]; x++) {
                int idx = y * W[1] + x;
                map[idx] = Integer.parseInt(tk.nextToken());
                if (map[idx] == RIPEN) {
                    q.offer(idx);
                    enqueued[idx] = true;
                    cnt++;
                }
                if (map[idx] != EMPTY)
                    tomato++;
            }
        }

        while (true) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                int x = q.poll();
                for (int d=1; d<=DIM; d++) {
                    for (int sgn=-1; sgn<=1; sgn+=2) {
                        int dx = sgn * P[d-1];
                        int nx = x + dx;
                        if ((P[d] + x) / P[d] != (P[d] + nx) / P[d]) continue;
                        if (map[nx] == EMPTY) continue;
                        if (enqueued[nx]) continue;

                        q.offer(nx);
                        enqueued[nx] = true;
                        map[nx] = RIPEN;
                        cnt++;
                    }
                }
            }
            if (q.isEmpty()) break;
            ans++;
        }

        if (cnt < tomato)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
}

메모리 및 시간

• 메모리: 100368 KB
• 시간: 340 ms

리뷰

• "구데기성"으로 악명 높은 구데기컵의 '하이퍼 토마토' 문제를 풀어보았다.
• 다차원 자료구조를 1차원으로 평탄화시켜야 쉬워진다는 점에서 의외로 실용적인 문제였다.
• 첫 시도는 임의차원 텐서를 N진 트리를 이용해 재귀적으로 정의하는 방법을 사용했는데, 재귀 때문인지 시간초과가 났다. (코드)
  • 이 코드는 7569번(3차원 토마토)는 겨우 통과했다. (358492 KB, 1336 ms)