๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด/DFS,BFS

[๋ฐฑ์ค€]7569๋ฒˆ: ํ† ๋งˆํ† 

by syLim___ 2023. 2. 28.
728x90

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

 

7569๋ฒˆ: ํ† ๋งˆํ† 

์ฒซ ์ค„์—๋Š” ์ƒ์ž์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋‘ ์ •์ˆ˜ M,N๊ณผ ์Œ“์•„์˜ฌ๋ ค์ง€๋Š” ์ƒ์ž์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” H๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. M์€ ์ƒ์ž์˜ ๊ฐ€๋กœ ์นธ์˜ ์ˆ˜, N์€ ์ƒ์ž์˜ ์„ธ๋กœ ์นธ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹จ, 2 โ‰ค M โ‰ค 100, 2 โ‰ค N โ‰ค 100,

www.acmicpc.net


7576 ํ† ๋งˆํ† ๋ž‘ ๊ฐ™์€ ๋ฌธ์ œ๋ผ์„œ ์–ด๋ ต์ง€ ์•Š๊ฒŒ ๋ฌธ์ œ๋ฅผ ๋งž์ถ”๊ธด ํ–ˆ๋‹ค.

 

๋‹ค๋งŒ ๋‚ด๊ฐ€ ๋ฆฌ์ŠคํŠธ์— ํ† ๋งˆํ†  ์ขŒํ‘œ์ •๋ณด๋ฅผ x,y,z ์ˆœ์„œ๊ฐ€ ์•„๋‹ˆ๋ผ z,x,y ์ˆœ์„œ๋กœ ์ €์žฅํ•ด์„œ ์•ฝ๊ฐ„ ํ—ท๊ฐˆ๋ฆด ์ˆ˜ ์žˆ๊ณ ,

์ฝ”๋“œ ๊ฐ€๋…์„ฑ์ด ์‚ด์ง ์ •์‹ ์‚ฌ๋‚˜์šด ๋А๋‚Œ

import sys
from collections import deque
input = sys.stdin.readline

#nํ–‰ m์—ด, ๋†’์ด๊ฐ€ h
m, n, h = map(int,input().split())

#ํ† ๋งˆํ† ๋ฐ•์Šค
storage=[]

for k in range(h):
  graph = []
  for i in range(n):
    graph.append(list(map(int,input().split())))
  storage.append(graph)

#storage[h][n][m]์œผ๋กœ ์ ‘๊ทผ!

#์ฒ˜์Œ๋ถ€ํ„ฐ ์ต์–ด ์žˆ๋Š” ํ† ๋งˆํ† ์œ„์น˜ (h,x,y)๋ฅผ ํ์— ์ €์žฅํ•˜๊ณ  bfs์ˆ˜ํ–‰
q=deque()

for k in range(h):
  for i in range(n):
    for j in range(m):
      if storage[k][i][j]==1:
        q.append((k,i,j))

#์ธ์ ‘ํ•œ 6๊ฐœ ์ขŒํ‘œ
dz = [0,0,0,0,1,-1]
dx = [-1,1,0,0,0,0]
dy = [0,0,-1,1,0,0]
while q:
  c,a,b = q.popleft()
  for i in range(6):
    nc = c+dz[i]
    na = a+dx[i]
    nb = b+dy[i]

    #๋ฒ”์œ„์กฐ๊ฑด ๋งŒ์กฑ, ์•„์ง ์•ˆ ์ต์€ ํ† ๋งˆํ† ๊ฐ€ ์žˆ๋‹ค๋ฉด ์ผ์ˆ˜๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ์คŒ
    if 0<=nc<h and 0<=na<n and 0<=nb<m:
      if storage[nc][na][nb]==0:
        storage[nc][na][nb] = storage[c][a][b]+1
        q.append((nc,na,nb))

result=0
for k in range(h):
  for i in range(n):
    for j in range(m):
      #์•ˆ ์ต์€ ํ† ๋งˆํ† ๊ฐ€ ์žˆ๋‹ค๋ฉด -1 ์ถœ๋ ฅ ํ›„ ์ข…๋ฃŒ
      if storage[k][i][j]==0:
        print(-1)
        exit()
      result = max(result,storage[k][i][j])

#bfs๋Œ๋ฉด์„œ ์ €์žฅ์‹œ์ผœ๋‘์—ˆ๋˜ ์ผ์ˆ˜ ์ค‘ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š”๋ฐ, ์ฒ˜์Œ์— 1์ด ์•„๋‹Œ 2๋ถ€ํ„ฐ ์นด์šดํŠธํ–ˆ์œผ๋‹ˆ 1์„ ๋นผ์ค€๋‹ค
print(result-1)
728x90