파이썬 알고리즘 285번 | [백준 7576번] 토마토 - BFS

285. 토마토

1) 어떤 전략(알고리즘)으로 해결?

BFS

2) 코딩 설명

주석 설명

<내 풀이>

from collections import deque
import sys
m,n = map(int,sys.stdin.readline().split())
farm = []
sum_chk = 0
disr = [-1,1,0,0]
disc = [0,0,-1,1]
q = deque()

for i in range(n) :
    chk = list(map(int,sys.stdin.readline().split()))
    farm.append(chk)
    
# 저장될 때부터 모든 토마토가 익어있는 상태이면 0
flag = -1
for i in range(n) :
    for j in range(m) :
        if farm[i][j] == 0 : 
            flag = 1
            break
# 만약 한번이라도 0 (안 익은 토마토) 마주치지 않음, 다 익은 상태
if flag == -1 : 
    print(0)
    exit(0)

# 익은 토마토 큐에 넣어주기 
for i in range(n) :
    for j in range(m) :
        if farm[i][j] == 1 : 
            q.append((i,j,0))
final_day=0

# BFS
while q : 
    r,c,day = q.popleft()
    if final_day<day : 
        final_day=day
    for i in range(4) :
        # 범위 맞고 아직 안 익은 토마토면 
        if 0<=r+disr[i]<n and 0<=c+disc[i]<m and farm[r+disr[i]][c+disc[i]]==0 :
            farm[r+disr[i]][c+disc[i]]=1 # 익게 해주고 
            q.append((r+disr[i], c+disc[i], day+1)) # 큐에 day+1 해서 넣어줌 

# while 끝났는데도 토마토가 모두 익지는 못하는 상황이면 -1을 출력 
for i in range(n) :
        for j in range(m) :
            if farm[i][j] == 0 : 
                print(-1)
                exit(0)
else : 
    print(final_day)

< 내 틀렸던 풀이, 문제점>

(1) 87% 에서 틀렸다고 뜸

from collections import deque
import sys
m,n = map(int,sys.stdin.readline().split())
farm = []
sum_chk = 0
disr = [-1,1,0,0]
disc = [0,0,-1,1]
q = deque()

for i in range(n) :
    chk = list(map(int,sys.stdin.readline().split()))
    farm.append(chk)
    sum_chk+=sum(chk)

if sum_chk == m*n : # 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력
    print(0)
    exit(0)
else : 
    for i in range(n) :
        for j in range(m) :
            if farm[i][j] == 1 : 
                q.append((i,j,0))
final_day=0

# BFS
while q : 
    r,c,day = q.popleft()
    if final_day<day : 
        final_day=day
    for i in range(4) :
        if 0<=r+disr[i]<n and 0<=c+disc[i]<m and farm[r+disr[i]][c+disc[i]]==0 :
            farm[r+disr[i]][c+disc[i]]=1
            q.append((r+disr[i], c+disc[i], day+1))

# 토마토가 모두 익지는 못하는 상황이면 -1을 출력 
for i in range(n) :
        for j in range(m) :
            if farm[i][j] == 0 : 
                print(-1)
                
else : 
    print(final_day)

=> 반례

이 부분에서 -1도 프린트 되고 final_day 도 프린트돼서 틀리고 있었음, 적절히 exit(0) 해주었다!

< 반례 >

3 3
1 0 0
0 0 -1
0 -1 0

답 :

-1 

내 출력 :

-1
2

<반성 점>

• 파이썬 런타임 에러 (NZEC) 은 exit(0) 이 아닌 다른 숫자로 지정해줄 시 난다.

<배운 점>

• exit(0) 처리 적절히 해주기