[알고리즘][Python] 백준(BOJ) 7569 토마토_파이썬

 

너비 우선 탐색

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

7569번: 토마토

 

 

문제 풀기 전 공부할 것 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

 

 

풀이 1

<내용>

• 토마토 정보를 저장할 box와 익은 토마토의 좌표를 넣을 grow를 선언한다.
• for문을 돌면서 box와 grow에 각각 토마토 값과 익은 토마토의 좌표를 넣어준다.
  • 이 부분이 이해가 안 되면 주석처리가 된 print 부분을 주석을 없애고 출력해보자.
• bfs이므로 deque로 문제를 해결하려 한다.
• que를 deque()로 정의하고 grow(익은 토마토의 좌표)를 넣는다.
• 함수 bfs를 선언한다.
  • que가 빌 때까지 익은 토마토의 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토가 익지 않은 토마토(값이 0인 토마토)인 경우 que에 넣어준다.
  • 해당 box[x][y][z]의 값은 box[hi][ro][co]보다 익는데 하루 더 걸리므로 +1을 한다.
• solve 함수를 정의한다.
  • 상자를 돌면서 익지 않은 토마토(값이 0인 토마토)가 있으면 -1을 리턴한다.
  • 그렇지 않으면 익는데 가장 오래 걸린 날짜를 출력한다.
• 마지막으로 처음부터 익은 토마토가 없는 경우 -1을 출력하고 그 이외의 경우는 solve 함수 결괏값을 출력한다.

 

 

<코드>

from collections import deque

m, n, h = map(int, input().split(' '))
box = [[] for _ in range(h)]
grow = []
for i in range(n*h):
    j = i // n
    row = list(map(int, input().split(' ')))
    box[j].append(row)
    for k in range(len(row)):
    	#print(j, i%n, k)
        if row[k] == 1:
            grow.append((j, i%n, k))

que = deque()
que += grow

def bfs():
    while que:
        hi, ro, co = que.popleft()
        for x, y, z in [(hi-1, ro, co), (hi+1, ro, co), (hi, ro-1, co), (hi, ro+1, co), (hi, ro, co-1), (hi, ro, co+1)]:
            if 0 <= x < h and 0 <= y < n and 0 <= z < m and box[x][y][z] == 0:
                box[x][y][z] = box[hi][ro][co] + 1
                que.append((x, y, z))

def solve():
    res = -1
    for i in range(h):
        for row in box[i]:
            if 0 in row:
                return -1
            else:
                res = max(res, max(row))
    return res-1

bfs()
if not grow:
    print(-1)
else:
    print(solve())

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 방법과 같다.
• 마지막에 res 구하는 과정에서 위의 함수와 다르게 break만 걸어주면 이중 for문이므로 익지 않은 토마토(값이 0인 토마토)가 있어도 -1 값이 나오지 않을 수 있다.
  • 반드시 flag를 통해 이중 for문을 나와야 한다.

 

 

<코드>

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

m, n, h = map(int, input().split())
box = [[] for _ in range(h)]
ripe = []
for i in range(n*h):
    j = i // n
    row = list(map(int, input().split(' ')))
    box[j].append(row)
    for k in range(len(row)):
        if row[k] == 1:
            ripe.append((j, i%n, k))

dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
que = deque()
que += ripe
while que:
    z, x, y = que.popleft()
    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
            if box[nz][nx][ny] == 0:
                box[nz][nx][ny] = box[z][x][y] + 1
                que.append((nz, nx, ny))

res = 0
flag = True
for i in range(h):
    if not flag:
        break
    for row in box[i]:
        if 0 in row:
            res = -1
            flag = False
            break
        else:
            res = max(res, max(row)-1)
if not ripe:
    res = -1
print(res)

 

 

 

 

 

 

 

 

해당 문제의 2차원 버전(더 쉬운 버전)

2021.07.16 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 7576 토마토_파이썬

[알고리즘][Python] 백준(BOJ) 7576 토마토_파이썬