백준 토마토 문제(7576, 7569) 파이썬

 

7576번: 토마토 (acmicpc.net)

7569번: 토마토 (acmicpc.net)

 

7576은 2차원 배열 안에서 bfs, 7569는 3차원 배열 안에서 bfs를 이용하여 풀었다. 

 

# 7576 소스코드

from collections import deque

def bfs(m, n):
    queue=deque()
    '''
    익은 토마토가 한 개보다 많을 수 있으므로
    bfs함수 이전에 이미 익어 있는 토마토의 위치를 모두 큐에 넣음. 
    '''
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                queue.append((i, j))

    while(queue):
        x, y = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if graph[nx][ny]==1:
                continue
            if graph[nx][ny]==-1:
                continue
            if graph[nx][ny]==0:
                graph[nx][ny]=graph[x][y]+1
                queue.append((nx, ny))

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

dx=[-1, 1, 0, 0]
dy=[0, 0, 1, -1]


bfs(m, n)

fail = False
res = -1

for i in graph:
    for j in i:
        if j == 0:
            fail=True
    res=max(res, max(i))

if fail: 
    print(-1)
else: print(res-1)

'''

m,n 입력 순서가 헷갈린다.

bfs 함수에서 리턴값을 받는 방식이 아니라 
함수 정의 --> 함수 한번 실행해서 그래프의 값들 업데이트 --> 따로 출력 조건 설정해서 출력
하는 게 어려웠다. 

'''

 

 

 

#7569 소스코드

from collections import deque


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

space=[[] for _ in range(h)]

for j in range(h):
    for i in range(n):
        space[j].append(list(map(int, input().split())))


dx=[1, -1, 0, 0, 0, 0]
dy=[0, 0, 1, -1, 0, 0]
dz=[0, 0, 0, 0, 1, -1]

def bfs(z, y, x):
    queue=deque()
    for i in range(z):
        for j in range(y):
            for k in range(x):
                if space[i][j][k]==1:
                    queue.append((i, j, k))
    while queue:
        z, y, x =  queue.popleft()
        for i in range(6):
            nz=z+dz[i]
            nx=x+dx[i]
            ny=y+dy[i]

            if nx>=0 and ny>=0 and nz>=0 and nx<m and ny<n and nz<h and space[nz][ny][nx] == 0:
                space[nz][ny][nx]=space[z][y][x]+1
                queue.append((nz, ny, nx))
            else:
                continue


bfs(h, n, m)
fail=False
res=-1
maxlist=[]
for i in space:
    for j in i:
        for k in j:
            if k==0:
                fail=True
                break
        maxlist.append(max(j))

res=max(res, max(maxlist))

if fail==False: 
    print(res-1)
else: print(-1)

 

3차원 배열을 구현하는 것부터 조금 헷갈리고, h, n, m 순서도 헷갈린다. 

앞 문제와 거의 비슷한 문제라 while queue 부분을 이차원 토마토보다 훨씬 간결하게 구현할 수 있었다.