μ•Œκ³ λ¦¬μ¦˜/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)