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
'์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด > DFS,BFS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค]14503๋ฒ: ๋ก๋ด ์ฒญ์๊ธฐ (0) | 2023.03.08 |
---|---|
[๋ฐฑ์ค]18405๋ฒ: ๊ฒฝ์์ ์ ์ผ (0) | 2023.03.03 |
[๋ฐฑ์ค]9205๋ฒ: ๋งฅ์ฃผ ๋ง์๋ฉด์ ๊ฑธ์ด๊ฐ๊ธฐ (0) | 2023.02.27 |
[๋ฐฑ์ค]11724๋ฒ: ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2023.02.26 |
[๋ฐฑ์ค]7576๋ฒ: ํ ๋งํ (0) | 2023.02.25 |