[BOJ] 17114번 하이퍼 토마토

[BOJ] 17114번 하이퍼 토마토 문제

매우 흔한 BFS 문제이다. 대신 11차원일 뿐이다... 2차원 토마토와 3차원 토마토 문제는 아래에 적어둔다.

• [BOJ] 7576번 토마토 문제 (2차원)
• [BOJ] 7569번 토마토 문제 (3차원)

---

핵심은 위의 두 문제와 별반 다르지 않다.

입력을 받고, 1인 곳의 좌표를 저장하고, 그 좌표에서 계속 BFS를 돌려서 값을 갱신하고, 다시 모든 좌표를 돌아 0이 나오면 -1을 출력 후 종료하고 아니라면 모든 좌표값 중 최댓값을 구하는 것이다.

위의 2차원과 3차원과의 차이가 있다면, 이 문제는 무려 11차원이다. 입력 받는 것부터가 장난이 아니다.

다만 차원만 높을 뿐이지 푸는 데에는 큰 차이가 없어서 복잡한 입력 처리 연습으로 매우 괜찮은 것 같다.

import sys
from collections import deque

def bfs():
    global m, n, o, p, q, r, s, t, u, v, w
    dm = [1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    dn = [0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    do = [0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    dp = [0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    dq = [0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    dr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ds = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0]
    dt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0]
    du = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0]
    dv = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0]
    dw = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1]

    while travel:
        n_m, n_n, n_o, n_p, n_q, n_r, n_s, n_t, n_u, n_v, n_w = travel.popleft()
        for i in range(22):
            next_m, next_n, next_o, next_p, next_q, next_r, next_s, next_t, next_u, next_v, next_w = n_m+dm[i], n_n+dn[i], n_o+do[i], n_p+dp[i], n_q+dq[i], n_r+dr[i], n_s+ds[i], n_t+dt[i], n_u+du[i], n_v+dv[i], n_w+dw[i]
            if is_in_range(next_m, next_n, next_o, next_p, next_q, next_r, next_s, next_t, next_u, next_v, next_w):
                if tomato[next_w][next_v][next_u][next_t][next_s][next_r][next_q][next_p][next_o][next_n][next_m] == 0:
                    tomato[next_w][next_v][next_u][next_t][next_s][next_r][next_q][next_p][next_o][next_n][next_m] = tomato[n_w][n_v][n_u][n_t][n_s][n_r][n_q][n_p][n_o][n_n][n_m] + 1
                    travel.append([next_m, next_n, next_o, next_p, next_q, next_r, next_s, next_t, next_u, next_v, next_w])


def is_in_range(n_m, n_n, n_o, n_p, n_q, n_r, n_s, n_t, n_u, n_v, n_w) -> bool:
    global m, n, o, p, q, r, s, t, u, v, w
    if 0 <= n_m < m and 0 <= n_n < n and 0 <= n_o < o and 0 <= n_p < p and 0 <= n_q < q and 0 <= n_r < r and 0 <= n_s < s and 0 <= n_t < t and 0 <= n_u < u and 0 <= n_v < v and 0 <= n_w < w:
        return True
    else:
        return False

if __name__ == '__main__':
    m, n, o, p, q, r, s, t, u, v, w = map(int, sys.stdin.readline().rstrip().split())
    tomato = list()
    for now_w in range(w):
        temp_w = list()
        for now_v in range(v):
            temp_v = list()
            for now_u in range(u):
                temp_u = list()
                for now_t in range(t):
                    temp_t = list()
                    for now_s in range(s):
                        temp_s = list()
                        for now_r in range(r):
                            temp_r = list()
                            for now_q in range(q):
                                temp_q = list()
                                for now_p in range(p):
                                    temp_p = list()
                                    for now_o in range(o):
                                        temp_o = list()
                                        for now_n in range(n):
                                            temp_o.append(list(map(int, sys.stdin.readline().rstrip().split())))
                                        temp_p.append(temp_o)
                                    temp_q.append(temp_p)
                                temp_r.append(temp_q)
                            temp_s.append(temp_r)
                        temp_t.append(temp_s)
                    temp_u.append(temp_t)
                temp_v.append(temp_u)
        temp_w.append(temp_v)
    tomato.append(temp_w)

    travel = deque()
    for now_w in range(w):
        for now_v in range(v):
            for now_u in range(u):
                for now_t in range(t):
                    for now_s in range(s):
                        for now_r in range(r):
                            for now_q in range(q):
                                for now_p in range(p):
                                    for now_o in range(o):
                                        for now_n in range(n):
                                            for now_m in range(m):
                                                if tomato[now_w][now_v][now_u][now_t][now_s][now_r][now_q][now_p][now_o][now_n][now_m] == 1:
                                                    travel.append([now_m, now_n, now_o, now_p, now_q, now_r, now_s, now_t, now_u, now_v, now_w])

    bfs()
    ans = -2
    for now_w in range(w):
        for now_v in range(v):
            for now_u in range(u):
                for now_t in range(t):
                    for now_s in range(s):
                        for now_r in range(r):
                            for now_q in range(q):
                                for now_p in range(p):
                                    for now_o in range(o):
                                        for now_n in range(n):
                                            for now_m in range(m):
                                                if tomato[now_w][now_v][now_u][now_t][now_s][now_r][now_q][now_p][now_o][now_n][now_m] == 0:
                                                    print(-1)
                                                    exit()

                                                ans = max(ans, tomato[now_w][now_v][now_u][now_t][now_s][now_r][now_q][now_p][now_o][now_n][now_m])

    print(ans-1)

 

자고로 이 코드의 총 길이는 공백을 제외하고 총 3060자다...