Python으로 구현한 7569번 토마토 문제 풀이입니다.
https://www.acmicpc.net/problem/7569
from collections import deque
m, n, h = map(int, input().split())
data = []
q = deque([])
result = 0
for k in range(h) :
arr = []
for i in range(n) :
arr.append(list(map(int, input().split())))
for j in range(m) :
if arr[i][j] == 1 : # 익은 토마토라면
q.append([k, i, j])
data.append(arr)
dx = [-1, 1, 0, 0, 0, 0] # 상 하 좌 우
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, 1, -1] # 앞 뒤 추가
def bfs() :
while q :
z, x, y = q.popleft()
for d in range(6) :
nz = z + dz[d]
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nz < h and 0 <= nx < n and 0 <= ny < m and data[nz][nx][ny] == 0 :
data[nz][nx][ny] = data[z][x][y] + 1
q.append([nz, nx, ny])
bfs()
flag = 0
for k in range(h) :
for i in range(n) :
for j in range(m) :
if data[k][i][j] == 0 :
print(-1)
exit(0)
result = max(result, max(data[k][i]))
print(result - 1)
1. 기존 https://www.acmicpc.net/problem/7576 문제와 비슷한 bfs() 방식으로 구현해주고, 이때 (앞 뒤) 방향만 더 확인해주면 된다.
2. h개의 각 n줄 창고 상태를 한 줄씩 입력받아 arr 리스트에 추가하고, 해당 줄의 m개의 토마토 중 익은 토마토의 층과 좌표를 q에 추가한 후 arr 리스트를 data 리스트에 추가한다.
3. (상, 하, 좌, 우, 앞, 뒤) 방향을 담은 dx, dy, dz 리스트를 정의하고 bfs() 함수를 호출하여 수행한다. bfs() 함수의 작업은 아래와 같다.
- q가 빌 때까지 좌표를 하나씩 꺼내(z, x, y) 여섯 가지 방향에 대한 각 다음 좌표를 확인한다.
- 다음 좌표가 창고 범위 내에 존재하고 해당 좌표에 있는 토마토가 안익었다면 해당 좌표(nz, nx, ny)를 q에 추가하고 원래의 좌표에 존재하는 data 값에 1을 더한 값을 data[nz][nx][ny]에 할당한다.
3. bfs() 함수의 작업이 끝나면 창고 상태를 한 줄씩 확인하고, 안익은 토마토가 있다면 -1을 출력한 후 시스템을 종료한다.
4. 한 줄을 확인했을 때 안익은 토마토가 없다면 result값과 현재 줄에 존재하는 최댓값을 비교하여 더 큰 값을 result에 할당한다.
5. 반복 작업이 끝나면 최종적으로 result에 1을 뺀 값을 출력한다. (가장 처음 0이 아닌 1부터 시작하였으므로)
'백준(Python) 풀이 > 그래프 이론' 카테고리의 다른 글
백준(Python) 2636번 치즈 풀이 (1) | 2022.09.26 |
---|---|
백준(Python) 9466번 텀 프로젝트 풀이 (0) | 2022.09.23 |
백준(Python) 7576번 토마토 풀이 (0) | 2022.09.21 |
백준(Python) 2206번 벽 부수고 이동하기 풀이 (1) | 2022.09.19 |
백준(Python) 2606번 바이러스 풀이 (0) | 2022.09.15 |