BOJ 17114 - 하이퍼 토마토 링크
(2023.08.16 기준 G1)

문제

11차원 창고의 크기가 주어지고 각 칸은 익은 토마토, 익지 않은 토마토, 빈 칸 중 하나이다.
하루가 지날 때마다, 익은 토마토에 인접한 익지 않은 토마토가 익는다. 이 때, 모든 토마토가 익는 최소 일수 출력

알고리즘

BFS 그리고 11차원 구현

풀이

11차원이라고 겁먹지 말자.
11차원으로 된 공간을 선언하고, 입력받고, 여느 BFS 문제처럼 BFS를 돌리면 된다.

2차원 행렬일 때에는 인접 방향은 (-1, 0), (1, 0), (0, -1), (0, 1) 이다.

그러면 11차원에선
(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, -1, 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, -1), (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1) 가 인접 방향이 된다. 하드 코딩하자.

코드

• C++

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

struct Dir{
    int dw, dv, du, dt, ds, dr, dq, dp, do_, dn, dm;
};

struct Element{
    int days, w, v, u, t, s, r, q, p, o, n, m;
};

// 토마토가 인접한 방향
Dir dir[22] = {{-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int M, N, O, P, Q, R, S, T, U, V, W;
    cin >> M >> N >> O >> P >> Q >> R >> S >> T >> U >> V >> W;

    int tomatoes[W][V][U][T][S][R][Q][P][O][N][M];
    for (int w = 0; w < W; w++) for (int v = 0; v < V; v++) for (int u = 0; u < U; u++) for (int t = 0; t < T; t++) for (int s = 0; s < S; s++) for (int r = 0; r < R; r++) for (int q = 0; q < Q; q++) for (int p = 0; p < P; p++) for (int o = 0; o < O; o++) for (int n = 0; n < N; n++) for (int m = 0; m < M; m++)
        cin >> tomatoes[w][v][u][t][s][r][q][p][o][n][m];

    // 먼저 익은 토마토를 찾아 queue에 넣자
    queue<Element> Queue;
    int rest = 0; // 익지 않은 토마토 개수도 찾아 저장
    for (int w = 0; w < W; w++) for (int v = 0; v < V; v++) for (int u = 0; u < U; u++) for (int t = 0; t < T; t++) for (int s = 0; s < S; s++) for (int r = 0; r < R; r++) for (int q = 0; q < Q; q++) for (int p = 0; p < P; p++) for (int o = 0; o < O; o++) for (int n = 0; n < N; n++) for (int m = 0; m < M; m++){
        if (tomatoes[w][v][u][t][s][r][q][p][o][n][m] == 1)
            Queue.push({0, w, v, u, t, s, r, q, p, o, n, m});
        else if (tomatoes[w][v][u][t][s][r][q][p][o][n][m] == 0)
            rest++;
    }

    // 토마토가 더 이상 익지 않을 때까지 bfs 반복
    int answer;
    while (!Queue.empty()){
        auto [days, w, v, u, t, s, r, q, p, o, n, m] = Queue.front(); Queue.pop();
        answer = days;
        for (auto [dw, dv, du, dt, ds, dr, dq, dp, do_, dn, dm]: dir)
            if (0 <= w + dw && w + dw < W && 0 <= v + dv && v + dv < V && 0 <= u + du && u + du < U && 0 <= t + dt && t + dt < T && 0 <= s + ds && s + ds < S && 0 <= r + dr && r + dr < R && 0 <= q + dq && q + dq < Q && 0 <= p + dp && p + dp < P && 0 <= o + do_ && o + do_ < O && 0 <= n + dn && n + dn < N && 0 <= m + dm && m + dm < M && tomatoes[w + dw][v + dv][u + du][t + dt][s + ds][r + dr][q + dq][p + dp][o + do_][n + dn][m + dm] == 0){
                Queue.push({days + 1, w + dw, v + dv, u + du, t + dt, s + ds, r + dr, q + dq, p + dp, o + do_, n + dn, m + dm});
                tomatoes[w + dw][v + dv][u + du][t + dt][s + ds][r + dr][q + dq][p + dp][o + do_][n + dn][m + dm] = 1;
                rest--;
            }
    }

    cout << (rest ? -1 : answer);
}

• Python

import sys; input = sys.stdin.readline
from collections import deque

# 토마토가 인접한 방향
dir = [(-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), \
       (0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0), \
       (0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0), \
       (0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0), \
       (0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0), \
       (0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0), \
       (0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0), \
       (0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0), \
       (0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0), (0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0), \
       (0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0), (0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0), \
       (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1), (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)]

M, N, O, P, Q, R, S, T, U, V, W = map(int, input().split())
tomatoes = [[[[[[[[[[list(map(int, input().split())) for _ in range(N)] for _ in range(O)] for _ in range(P)] for _ in range(Q)] for _ in range(R)] for _ in range(S)] for _ in range(T)] for _ in range(U)] for _ in range(V)] for _ in range(W)]

# 먼저 익은 토마토를 찾아 deque에 넣자
queue = deque(); rest = 0 # 익지 않은 토마토 개수도 찾아 저장
for w in range(W):
    for v in range(V):
        for u in range(U):
            for t in range(T):
                for s in range(S):
                    for r in range(R):
                        for q in range(Q):
                            for p in range(P):
                                for o in range(O):
                                    for n in range(N):
                                        for m in range(M):
                                            if tomatoes[w][v][u][t][s][r][q][p][o][n][m] == 1:
                                                queue.append((0, w, v, u, t, s, r, q, p, o, n, m))
                                            elif tomatoes[w][v][u][t][s][r][q][p][o][n][m] == 0:
                                                rest += 1

# 토마토가 더 이상 익지 않을 때까지 bfs 반복
while queue:
    days, w, v, u, t, s, r, q, p, o, n, m = queue.popleft()
    for dw, dv, du, dt, ds, dr, dq, dp, do, dn, dm in dir:
        if 0 <= w + dw < W and 0 <= v + dv < V and 0 <= u + du < U and 0 <= t + dt < T and 0 <= s + ds < S and 0 <= r + dr < R and 0 <= q + dq < Q and 0 <= p + dp < P and 0 <= o + do < O and 0 <= n + dn < N and 0 <= m + dm < M and tomatoes[w + dw][v + dv][u + du][t + dt][s + ds][r + dr][q + dq][p + dp][o + do][n + dn][m + dm] == 0:
            queue.append((days + 1, w + dw, v + dv, u + du, t + dt, s + ds, r + dr, q + dq, p + dp, o + do, n + dn, m + dm))
            tomatoes[w + dw][v + dv][u + du][t + dt][s + ds][r + dr][q + dq][p + dp][o + do][n + dn][m + dm] = 1
            rest -= 1

print(-1 if rest else days)