๐ญ ๋ฌธ์ ์ดํด
์ญ์ ํ์๋ฌธ์ ๋ก BFS๋ฅผ ์ด์ฉํ์ฌ ํ์ด์ผ ํ๋ค.
์ฌ์ฏ ๋ฐฉํฅ์ผ๋ก ๋์์ ์งํํ๋ฏ๋ก ๋๋น ์ฐ์ ํ์์ด ๋ง๋ค๊ณ ํ๋จํ์๋ค.
๋ค๋ฅธ ๋ฌธ์ ์ ์ฐจ์ด์ ์ด๋ผ๋ฉด 3์ฐจ์ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ์ฌ์ผ ํ๋ค๋ ์ ์ธ๋ฐ,
arr[๊น์ด][๊ฐ๋ก][์ธ๋ก] ์ธ ๊ฒ์ ์ ์ํ์ฌ์ผ ํ๋ ๋ฌธ์ ์ด๋ค.
๊ตฌํ ์ธ์ด: Python
import sys
from collections import deque
# 3์ฐจ์ ๋ฆฌ์คํธ๋ arr[๊น์ด][๊ฐ๋ก][์ธ๋ก]๋ก ๊ตฌ์ฑ
# col, rol, height
m, n, h = map(int, sys.stdin.readline().rstrip().split())
warehouse = [[list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] for _ in range(h)]
queue = deque()
# ์ ํ ์ข ์ฐ ์ ๋ค
mx = [-1, 1, 0, 0, 0, 0]
my = [0, 0, -1, 1, 0, 0]
mz = [0, 0, 0, 0, -1, 1]
# ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ด์๋ ์ํ ์ฒดํฌ
all_ripen = True
for level in warehouse:
for row in level:
if 0 in row:
all_ripen = False
if all_ripen:
print(0)
sys.exit()
last_val = 0
for k in range(h):
for i in range(n):
for j in range(m):
if warehouse[k][i][j] == 1:
queue.append((k, i, j))
while queue:
z, x, y = queue.popleft()
for t in range(6):
nx = x + mx[t]
ny = y + my[t]
nz = z + mz[t]
if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
if warehouse[nz][nx][ny] == 0:
warehouse[nz][nx][ny] = warehouse[z][x][y] + 1
last_val = warehouse[nz][nx][ny]
queue.append((nz, nx, ny))
# ์์
๋๋ ํ ํ ๋งํ ์ํ ์ฒดํฌ
all_ripen = True
for level in warehouse:
for row in level:
if 0 in row:
all_ripen = False
if not all_ripen:
print(-1)
else:
# ์์์ผ์ ํฌํจํ ๊ฐ์ด๋ฏ๋ก -1
print(last_val - 1)
'Problem_Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] ๋ฐฑ์ค 12851 ์จ๋ฐ๊ผญ์ง 2 / BFS (0) | 2021.01.12 |
---|---|
[BOJ] ๋ฐฑ์ค 1697 ์จ๋ฐ๊ผญ์ง / BFS (0) | 2021.01.07 |
[BOJ] ๋ฐฑ์ค 2644 ์ด์๊ณ์ฐ / BFS, DFS (0) | 2021.01.05 |
[BOJ] ๋ฐฑ์ค 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ / BFS, DFS (0) | 2021.01.04 |
[BOJ] ๋ฐฑ์ค 2887 ํ์ฑ ํฐ๋ / ์ต์ ์ ์ฅ ํธ๋ฆฌ(MST), ํฌ๋ฃจ์ค์นผ (0) | 2020.11.21 |