π ν λ§ν (3μ°¨μ)
λ°±μ€ Class3 Gold5
solved_ac[Class3] ν λ§ν
λ¬Έμ
μ² μμ ν λ§ν λμ₯μμλ ν λ§ν λ₯Ό 보κ΄νλ ν° μ°½κ³ λ₯Ό κ°μ§κ³ μλ€. ν λ§ν λ μλμ κ·Έλ¦Όκ³Ό κ°μ΄ 격μλͺ¨μ μμμ μΉΈμ νλμ© λ£μ λ€μ, μμλ€μ μμ§μΌλ‘ μμ μ¬λ €μ μ°½κ³ μ 보κ΄νλ€.
μ°½κ³ μ 보κ΄λλ ν λ§ν λ€ μ€μλ μ μ΅μ κ²λ μμ§λ§, μμ§ μ΅μ§ μμ ν λ§ν λ€λ μμ μ μλ€. λ³΄κ΄ ν νλ£¨κ° μ§λλ©΄, μ΅μ ν λ§ν λ€μ μΈμ ν κ³³μ μλ μ΅μ§ μμ ν λ§ν λ€μ μ΅μ ν λ§ν μ μν₯μ λ°μ μ΅κ² λλ€. νλμ ν λ§ν μ μΈμ ν κ³³μ μ, μλ, μΌμͺ½, μ€λ₯Έμͺ½, μ, λ€ μ¬μ― λ°©ν₯μ μλ ν λ§ν λ₯Ό μλ―Ένλ€. λκ°μ λ°©ν₯μ μλ ν λ§ν λ€μκ²λ μν₯μ μ£Όμ§ λͺ»νλ©°, ν λ§ν κ° νΌμ μ μ λ‘ μ΅λ κ²½μ°λ μλ€κ³ κ°μ νλ€. μ² μλ μ°½κ³ μ 보κ΄λ ν λ§ν λ€μ΄ λ©°μΉ μ΄ μ§λλ©΄ λ€ μ΅κ² λλμ§ κ·Έ μ΅μ μΌμλ₯Ό μκ³ μΆμ΄ νλ€.
ν λ§ν λ₯Ό μ°½κ³ μ 보κ΄νλ 격μλͺ¨μμ μμλ€μ ν¬κΈ°μ μ΅μ ν λ§ν λ€κ³Ό μ΅μ§ μμ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ‘μ λ, λ©°μΉ μ΄ μ§λλ©΄ ν λ§ν λ€μ΄ λͺ¨λ μ΅λμ§, κ·Έ μ΅μ μΌμλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ. λ¨, μμμ μΌλΆ μΉΈμλ ν λ§ν κ° λ€μ΄μμ§ μμ μλ μλ€.
μ λ ₯
첫 μ€μλ μμμ ν¬κΈ°λ₯Ό λνλ΄λ λ μ μ M,Nκ³Ό μμμ¬λ €μ§λ μμμ μλ₯Ό λνλ΄λ Hκ° μ£Όμ΄μ§λ€. Mμ μμμ κ°λ‘ μΉΈμ μ, Nμ μμμ μΈλ‘ μΉΈμ μλ₯Ό λνλΈλ€. λ¨, 2 β€ M β€ 100, 2 β€ N β€ 100, 1 β€ H β€ 100 μ΄λ€. λμ§Έ μ€λΆν°λ κ°μ₯ λ°μ μμλΆν° κ°μ₯ μμ μμκΉμ§μ μ μ₯λ ν λ§ν λ€μ μ λ³΄κ° μ£Όμ΄μ§λ€. μ¦, λμ§Έ μ€λΆν° Nκ°μ μ€μλ νλμ μμμ λ΄κΈ΄ ν λ§ν μ μ λ³΄κ° μ£Όμ΄μ§λ€. κ° μ€μλ μμ κ°λ‘μ€μ λ€μ΄μλ ν λ§ν λ€μ μνκ° Mκ°μ μ μλ‘ μ£Όμ΄μ§λ€. μ μ 1μ μ΅μ ν λ§ν , μ μ 0 μ μ΅μ§ μμ ν λ§ν , μ μ -1μ ν λ§ν κ° λ€μ΄μμ§ μμ μΉΈμ λνλΈλ€. μ΄λ¬ν Nκ°μ μ€μ΄ Hλ² λ°λ³΅νμ¬ μ£Όμ΄μ§λ€.
ν λ§ν κ° νλ μ΄μ μλ κ²½μ°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
μ¬λ¬λΆμ ν λ§ν κ° λͺ¨λ μ΅μ λκΉμ§ μ΅μ λ©°μΉ μ΄ κ±Έλ¦¬λμ§λ₯Ό κ³μ°ν΄μ μΆλ ₯ν΄μΌ νλ€. λ§μ½, μ μ₯λ λλΆν° λͺ¨λ ν λ§ν κ° μ΅μ΄μλ μνμ΄λ©΄ 0μ μΆλ ₯ν΄μΌ νκ³ , ν λ§ν κ° λͺ¨λ μ΅μ§λ λͺ»νλ μν©μ΄λ©΄ -1μ μΆλ ₯ν΄μΌ νλ€.
μμ μ λ ₯ 1
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
μμ μΆλ ₯ 1
-1
μμ μ λ ₯ 2
5 3 2
0 0 0 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
μμ μΆλ ₯ 2
4
μμ μ λ ₯ 3
4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1
μμ μΆλ ₯ 3
0
π μλ£κ΅¬μ‘°
https://happyyeon.github.io/algorithm/2022-05-19-tomato/ μ°Έμ‘°
μμ μ νμλ ν λ§ν λ¬Έμ λ 2μ°¨μμ΄μλ€λ©΄ μ΄λ²μλ λμΌν 쑰건μ 3μ°¨μ λ¬Έμ μλ€. λκ°μ΄ BFSλ‘ νμλ€.
π¨π»βπ» CODE
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
# μ΄κΈ° 쑰건
m,n,h = map(int,input().split())
tomato = [[list(map(int,input().split())) for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
for j in range(n):
for k in range(m):
if tomato[i][j][k] == 1:
q.append((i,j,k))
dx = [1,-1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]
def bfs(tomato):
while q:
i,j,k = q.popleft()
for dir in range(6):
x = i+dx[dir]
y = j+dy[dir]
z = k+dz[dir]
if 0<=x<h and 0<=y<n and 0<=z<m and tomato[x][y][z] == 0:
tomato[x][y][z] = tomato[i][j][k] + 1
q.append((x,y,z))
def check_zero(tomato):
for i in range(h):
for j in tomato[i]:
if 0 in j:
return True
return False
def check_day(tomato):
day = -1*INF
for i in range(h):
for j in tomato[i]:
day = max(max(j),day)
return day
bfs(tomato)
if check_zero(tomato):
print(-1)
else:
print(check_day(tomato)-1)