[Baekjoon] 7576번 : 토마토 (Python)

[Baekjoon] 7576번 : 토마토 (Python)

 

목차

 

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

7576번: 토마토

Python

 

방법 1 - 메모리 97972KB / 시간 2280ms / 코드 길이 775B

 

일반적인 BFS와는 조금 다른 것이 토마토를 다 키우는 일수를 구하기 위해 queue를 초기에 넣어주고 그 다음 bfs로 넘어가야한다는 점이다. 그외 진행에 따라 graph에 숫자를 키우고 최대 일수를 구하는 방식으로 진행하면 된다.

 

물론 불가능할 때는 -1을 출력하기 위한 for문을 구성하기도 해야한다.

 

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

m,n = map(int, input().split())
l = []
q = deque()

for i in range(n):
    l.append(list(map(int, input().split())))
    for j in range(m):
        if l[i][j] == 1:
            q.append((i,j))

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

def bfs():

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1:
                continue

            if l[nx][ny] == 0:
                l[nx][ny] = l[x][y] + 1
                q.append((nx, ny))

bfs()
ans = 0
for i in l:
    for j in i:
        if j ==0:
            print(-1)
            exit(0)
    ans = max(ans, max(i))

print(ans - 1)

  

방법 2 - 92%에서 런타임 에러 (UnboundLocalError)로 실패 - 코드 길이 873B

 

초기 시도했던 방법으로 count를 위한 추가 할당을 진행하였다. 

다만 92%에서 발생한 런타임 에러 (UnboundLocalError)로 인하여 해결하지 못하고 아래 적어두고자 한다.

문제를 아시는 분 답 좀...

 

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

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

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

def bfs(one_loc):
    q = deque()
    for i in range(len(one_loc)):
        q.append(one_loc[i])

    while q:
        x, y, c = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1:
                continue

            if l[nx][ny] == 0:
                l[nx][ny] = 1
                q.append((nx, ny, c+1))
    return c

one_loc = []
for i in range(n):
    for j in range(m):
        if l[i][j] == 1:
            one_loc.append((i,j,0))

cnt = bfs(one_loc)

for i in l:
    if 0 in i:
        print(-1)
        exit(0)

print(cnt)