μκ³ λ¦¬μ¦/DFS BFS
[Python] λ°±μ€ 7569 ν λ§ν
JayAlex07
2023. 2. 13. 13:57
π§βπ» [Python] λ°±μ€ 7569 ν λ§ν
Gold 5 - BFS
무쑰건 BFSλ‘ νμ΄μΌ νλ λ¬Έμ μ΄λ€
μμμ μ΄ νλκ° μλ μ μλ€
- κ·Έλμ queue μμλ€ μμμ λ€μ λͺ¨λ μ°Ύμμ λ£λλ€
BFSλ₯Ό ν λλ§λ€ μ£Όλ³ λ Έλμλ€ λ°©λ¬Έ νμ λμ 1μ λν΄μ, λν μ«μλ₯Ό λ£λλ€
λ§μ§λ§μ λ€μ νμμ ν΄μΌνλλ°, 0μ΄ νλλΌλ μμΌλ©΄ -1μ μΆλ ₯νκ³ , κ·Έκ² μλλ©΄ λν μ«μλ€ μ€ μ μΌ ν° μ«μμ 1μ λΉΌμ, λ΅μ μΆλ ₯νλ€
7576κ³Ό κ°μ λ¬Έμ μ΄μ§λ§, λμ΄κ° μΆκ°κ° λμλ€
- 3μ€ ν¬λ¬Έμ μ°λ, 3μ€ λ¦¬μ€νΈ μ¬μ©λ²μ μ΅νμΌ ν
λ¬Έμ νμ΄
bfs
μ- μ£Όλ³μ νμνκ³ , μ£Όλ³μ μλ λ
Έλ μμ£Όλ‘ νμνκΈ° μν΄
popleft
λ₯Ό μ¬μ©
- μ£Όλ³μ νμνκ³ , μ£Όλ³μ μλ λ
Έλ μμ£Όλ‘ νμνκΈ° μν΄
- 첫 for문
queue
μλ€κ° μμ μ λ€μ λ£λλ€- μμμ μ΄ νλμΌ λμλ forλ¬Έμ λ릴 νμκ° μμ§λ§, μ΄ λ¬Έμ μμλ μμμ μ΄ 1κ° μ΄μμ΄ μ£Όμ΄μ§ μ μλ€
- λλ²μ§Έ forλ¬Έ
- κ²°κ³Όκ°μ νμνλ€
- bfsλ₯Ό λ€ λκ³ λλ©΄, boxμ λͺ μΌμ΄ μ§λ¬λμ§, μ«μλ€μ΄ νκΈ°λμ΄ μλ€
- κ° μ΄μ λλ©°, μ΄μμ μ μΌ ν° μ«μλ₯Ό
answer
μ μ μ₯μ νλ€ - λ¨, 0μ΄ νλλΌλ λ°κ²¬μ΄ λλ€λ©΄,
flag
λ Falseλ‘ λ°κΎΌλ€- μ΄ λ»μ, λͺ¨λ ν λ§ν κ° λ€ μ΅μ§ λͺ» νλ€λ κ²μ΄λ€
- μ¦ -1μ μΆλ ₯ν΄μΌ νλ€
μ½λ
from collections import deque
def bfs(queue):
while queue:
current_h, current_r, current_c = queue.popleft()
for i in range(6):
sh, sr, sc = current_h + dh[i], current_r + dr[i], current_c + dc[i]
if 0 <= sr < N and 0 <= sc < M and 0 <= sh < H:
if box[sh][sr][sc] == 0 and box[sh][sr][sc] != -1:
box[sh][sr][sc] = box[current_h][current_r][current_c] + 1
queue.append((sh, sr, sc))
M, N, H = map(int, input().split())
box = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
queue = deque([])
# λΆμλλ¨, μ μλ
dh, dr, dc= [0, 0, 0, 0, -1, 1], [-1, 0, 0, 1, 0, 0], [0, -1, 1, 0, 0, 0]
answer = 0
# queueμλ€ μμ μ λ€ λ£κΈ°
for h in range(H):
for r in range(N):
for c in range(M):
if box[h][r][c] == 1:
queue.append((h, r, c))
bfs(queue)
flag = True
for h in range(H):
if flag == False:
break
for r in range(N):
if flag == False:
break
for c in range(M):
if box[h][r][c] == 0:
flag = False
break
answer = max(answer, max(box[h][r]))
if flag == False:
print(-1)
else:
print(answer -1)