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

 

너비 우선 탐색

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

7576번: 토마토

 

 

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

 

 

 

 

 

 

 

풀이 1

<내용>

• 먼저 box에 토마토 정보를 저장한다.
• 그리고 익은 토마토를 ripe에 넣어준다.
  • 이중 for문으로 box를 돌면서 값이 1인 익은 토마토를 확인하고 해당 위치를 ripe에 넣는다.
• dx, dy는 해당 토마토와 인접한 곳(왼쪽, 오른쪽, 앞, 뒤) 네 방향을 확인하기 위한 것이다.
• que를 deque()로 정의한다. (bfs이기 때문에 deque를 활용한다.)
• que에 ripe(익은 토마토)를 넣어주고 que가 빌 때까지 popleft를 해준다.(먼저 들어간 것이 먼저 나오도록)
• 익은 토마토의 왼쪽, 오른쪽, 앞, 뒤 방향의 토마토도 익게 만들어주므로 for문을 활용하여 상자 범위 안에 있고 익지 않은 토마토(값이 0인 토마토)를 확인하여 익도록 만들어 준다. 그리고 해당 토마토는 익었으므로 que에 넣어준다.
• 모두 익을 때까지의 최소 날짜를 출력해야 하므로 상자를 돌면서 익지 않은 토마토(값이 0인 토마토)가 있으면 -1을 출력하고 그렇지 않다면 상자의 숫자들은 익는데 걸린 날짜 + 1 이므로 익는데 가장 오래 걸린 값을 출력한다.

 

 

<코드>

from collections import deque

m, n = map(int, input().split(' '))
box = []
for _ in range(n):
    box.append(list(map(int, input().split(' '))))

ripe = []
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            ripe.append((i, j))

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

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

res = 0
for row in box:
    if 0 in row:
        res = -1
        break
    else:
        res = max(res, max(row)-1)

print(res)

 

 

 

 

풀이 2

<내용>

• 풀이는 위의 내용과 동일하다.
• 위의 해당 내용을 함수로 만들어 표현한 것이다.

 

 

<코드>

from collections import deque

m, n = map(int, input().split(' '))  # m : 가로, n : 세로
tomato = []
for _ in range(n):
    tomato.append(list(map(int, input().split(' '))))

grow = []
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            grow.append((i, j))


que = deque()
que += grow

def bfs():
    while que:
        i, j = que.popleft()
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= x < n and 0 <= y < m:
                if tomato[x][y] == 0:
                    tomato[x][y] = tomato[i][j] + 1
                    que.append((x, y))

def solve():
    res = 0
    for i in range(n):
        for j in range(m):
            if tomato[i][j] == 0:
                return -1
            else:
                res = max(res, tomato[i][j])
    return res-1

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