백준 7569 토마토

gmlwlswldbs·2022년 1월 6일
0

코딩테스트

목록 보기
95/130
from collections import deque
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

m, n, h = map(int, input().split())
g = []

for i in range(h):
    tmp_g = [list(map(int, input().split())) for _ in range(n)]
    g.append(tmp_g)

check = [[[-1] * m for _ in range(n)] for _ in range(h)]

def bfs(i, j, k):
    q = deque()
    check[i][j][k] = 0
    q.append((i, j, k))
    while q:
        a, b, c = q.popleft()
        for d in range(6):
            na, nb, nc = a + dx[d], b + dy[d], c + dz[d]
            if 0 <= na < h and 0 <= nb < n and 0 <= nc < m:
                if check[na][nb][nc] == -1 and g[na][nb][nc] == 0:
                    q.append((na, nb, nc))
                    check[na][nb][nc] = check[a][b][c] + 1
                    g[na][nb][nc] = 1

for i in range(h):
    for j in range(n):
        for k in range(m):
            if check[i][j][k] == -1 and g[i][j][k] == 1:
                bfs(i, j, k)

ans = 0
notall = False
for i in range(h):
    for j in range(n):
        for k in range(m):
            if g[i][j][k] == 0:
                notall = True
            else:
                ans = max(ans, check[i][j][k])
if notall:
    print(-1)
else:
    print(ans)

처음에 틀린 코드
이유 : 영향을 받아서 익는게 동시에 일어난다고 생각해야하는데 순차적으로 일어난다고 코드를 짜서 틀림 (bfs 돌릴 때 기존의 토마토가 있던 곳은 한번에 넣고 동시에 탐색해야한다)
반례 )
3 3 1
1 1 0
0 0 0
0 0 0
정답 : 3 내 출력 : 4

from collections import deque
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]

m, n, h = map(int, input().split())
g = []

for i in range(h):
    tmp_g = [list(map(int, input().split())) for _ in range(n)]
    g.append(tmp_g)

check = [[[-1] * m for _ in range(n)] for _ in range(h)]

def bfs():
    q = deque()
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if check[i][j][k] == -1 and g[i][j][k] == 1:
                    check[i][j][k] = 0
                    q.append((i, j, k))
    while q:
        a, b, c = q.popleft()
        for d in range(6):
            na, nb, nc = a + dx[d], b + dy[d], c + dz[d]
            if 0 <= na < h and 0 <= nb < n and 0 <= nc < m:
                if check[na][nb][nc] == -1 and g[na][nb][nc] == 0:
                    q.append((na, nb, nc))
                    check[na][nb][nc] = check[a][b][c] + 1
                    g[na][nb][nc] = 1

bfs()

ans = 0
notall = False
for i in range(h):
    for j in range(n):
        for k in range(m):
            if g[i][j][k] == 0:
                notall = True
            else:
                ans = max(ans, check[i][j][k])
if notall:
    print(-1)
else:
    print(ans)

수정 코드 : 기존의 토마토들은 한번에 큐에 넣었다. 이 부분 꼭 주의해서 논리적 오류 없애기

0개의 댓글