[Python] 17114번 하이퍼 토마토

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

17114번: 하이퍼 토마토

---

 

22/10/11

 

 

기존 토마토 문제(7576번, 7569번)와 기본적인 접근 방법 자체는 똑같다. 하지만, 11차원으로 인해 생기는 시간 부족을 관리해야 되기 때문에 약간 코드가 다르게 적을 수밖에 없었다.

 

2022.09.20 - [백준 문제 풀이] - [Python] 7576번 토마토

[Python] 7576번 토마토

2022.10.24 - [백준 문제 풀이] - [Python] 7569번 토마토

[Python] 7569번 토마토

---

 

문제 접근 방식:

 

 

기존에 풀었던 토마토 문제는 compare이라는 0이 다 1로 채워진 그래프를 따로 만들어 그 그래프랑 비교하는 방식을 취했었는데, 이 문제는 그렇게 하면 시간 초과를 받는다.

 

왜냐하면 O(n^2)의 시간복잡도를 지니기 때문이다.

 

compare그래프를 만드는데 O(n^2), 비교하는 데에도 O(n^2)의 시간이 소요되기 때문이다.

 

결국, 우리는 그래프가 -1을 제외한 부분만 전부 1로 채워지기를 원한다.

 

때문에, count이라는 변수를 m부터 w까지 전부 다 곱한 값으로 초기화시켜주었다.

 

이는 그 그래프의 0의 개수를 의미한다.

 

먼저 그래프를 입력받을 때 1이나 -1을 입력받으면 count에 1을 빼줌으로써, count가 현재 0이 몇 개가 있는지 나타내도록 만들어주었다.

 

이후 BFS를 진행하면서 0을 1로 바꾸는 작업을 하는데, 1로 바꿀 때마다, count변수에 1을 빼주는 작업을 진행한다.

 

우리는 모든 토마토가 익기를, 즉, 모든 안 익은 토마토(0)가 익은 토마토(1)로 바뀌어지길 원하기 때문에, 만약 정상적으로 모든 토마토가 익었다면 count변수가 0이 될 것이다.

 

때문에 이를 이용하여 O(n)의 시간 복잡도로 모든 토마토가 익었는지 안 익었는지를 판단하는 코드를 구성할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17114번 하이퍼 토마토
# 그래프 이론, 그래프 탐색, BFS
import sys
input = lambda: sys.stdin.readline().rstrip()
# input = iter(open(0).read().split("\n")).__next__
from collections import deque
from itertools import product

m, n, o, p, q, r, s, t, u, v, w = map(int, input().split())
graph = [[[[[[[[[[[] 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)]
count = m*n*o*p*q*r*s*t*u*v*w
queue = deque()

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):
                                        a = list(map(int, input().split()))
                                        for M in range(m):
                                            if a[M] == 1:
                                                queue.append([W, V, U, T, S, R, Q, P, O, N, M, 0])
                                                count -= 1
                                            elif a[M] == -1:
                                                count -= 1
                                            graph[W][V][U][T][S][R][Q][P][O][N].append(a[M])

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]
                                  
final_time = 0
while queue:
    W, V, U, T, S, R, Q, P, O, N, M, time = queue.popleft()
    for i in range(22):
        nm, nn, no, np, nq, nr, ns, nt, nu, nv, nw = M + dm[i], N + dn[i], O + do[i], P + dp[i], Q + dq[i], R + dr[i], S + ds[i], T + dt[i], U + du[i], V + dv[i], W + dw[i]
        if (nw < 0 or nw >= w or nv < 0 or nv >= v or nu < 0 or nu >= u or nt < 0 or nt >= t or
            ns < 0 or ns >= s or nr < 0 or nr >= r or nq < 0 or nq >= q or np < 0 or np >= p or
            no < 0 or no >= o or nn < 0 or nn >= n or nm < 0 or nm >= m):
            continue
        if not graph[nw][nv][nu][nt][ns][nr][nq][np][no][nn][nm]:
            graph[nw][nv][nu][nt][ns][nr][nq][np][no][nn][nm] = 1
            count -= 1
            queue.append([nw, nv, nu, nt, ns, nr, nq, np, no, nn, nm, time+1])
            if final_time < time+1:
                final_time = time+1

if count == 0:
    print(final_time)
else:
    print(-1)