[BOJ-7576] 토마토

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

7576번: 토마토

---

[ 코드1] 

# -*- coding: utf-8 -*-
# 7576. 토마토
import sys
from collections import deque
input= sys.stdin.readline

M,N=0,0
visited=None
tomato=None
q=deque()

dy=[-1,1,0,0] #상하좌우
dx=[0,0,-1,1]

def isRange(y, x):
    global M,N
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global visited, tomato
    last_day=0
    while q:
        y,x, days= q.popleft()
        visited[y][x]=True
        last_day=days
        
        for i in range(4):
            nexty=dy[i]+y
            nextx=dx[i]+x
            if isRange(nexty, nextx):
                #아직방문을 안했고, 안익은 토마토라면
                if (not visited[nexty][nextx]) and (tomato[nexty][nextx]==0):
                    tomato[nexty][nextx]=1 #토마토가 익었다.
                    q.append((nexty, nextx, days+1))
    return last_day
                
def main():
    global M,N, visited, tomato
    M,N =map(int, input().split()) #M: 가로길이, N: 세로 길이
    tomato=[ [*map(int, input().split())] for _ in range(N)]

    #1. 안익은 토마토가 있는지 확인
    not_rotten=0 #안익은 토마토 개수
    for y in range(N):
        for x in range(M):
            if tomato[y][x]==0:
                not_rotten+=1
                break
            
    #모두다 익은 토마토
    if not_rotten==0:
        print(0)

    else:
        #2. 익은 토마토의 위치를 찾아서 큐에 넣는다.
        for y in range(N):
            for x in range(M):
                if tomato[y][x]==1:
                    q.append((y,x,0))

        #BFS()탐색을 한다.
        #visited 방문리스트를 만든다.
        visited=[ [False]*M for _ in range(N)]
        result=bfs()

        #3. 안익은 토마토를 찾는다.
        not_rotten=0 #안익은 토마토 개수
        for y in range(N):
            for x in range(M):
                if tomato[y][x]==0:
                    not_rotten+=1
                    break
                
        if not_rotten==1:#안익은 토마토가 있다면 -1을 출력
            print(-1)
        else:#안익은 토마토가 없다면 result값을 출력
            print(result)


if __name__=='__main__':
    main()

---

[코드2]

2주일전에 작성한 코드도 같이 ㅎㅎ~

# -*- coding: utf-8 -*-
import sys
from collections import deque
#M:가로(열), N:세로(행)
#tomatoes: 토마토
M,N= map(int, sys.stdin.readline().split())
tomatoes=[ list(map(int,sys.stdin.readline().split()))  for _ in range(N)]
q=deque()
visited=[ [False]*M for _ in range(N)]

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

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

def bfs():
    global visited, tomatoes
    while q:
        cury, curx, day=q.popleft()
        if not visited[cury][curx]:
            #방문하지 않았다면, 방문상태로 만든다.
            visited[cury][curx]=True

            #(cury, curx)의 상하좌우를 찾는다
            #그 상/하/좌/우가 적절한 위치인지 확인한다.
            for i in range(4):
                nexty=cury+dy[i]
                nextx=curx+dx[i]

                #(nexty, nextx)가 적절한 위치에 있는가?
                if isRange(nexty, nextx):
                    #(nexty, nextx)에 위치한 토마토가
                    #아직 방문하지 않은 상태이고, 익지않은 토마토(0)이라면
                    if (tomatoes[nexty][nextx]==0) and (not visited[nexty][nextx]):
                        tomatoes[nexty][nextx]=1 #그토마토는 이제 익은상태로 한다.
                        q.append((nexty, nextx, day+1)) #큐에 넣는다.
    return day

def print_tomatoes():
    global tomatoes
    for t in tomatoes:
        print(t)
    print()

def main():
    global N,M, tomatoes, visited
    #1. 안익은 토마토(0)가 있는지 확인한다
    day=0 #모든 토마토가 익을 때까지 걸린시간(일)
    cnt_green=0
    for y in range(N):
        for x in range(M):
            #안익은 토마토가 있다면 나간다.
            if tomatoes[y][x]==0:
                cnt_green+=1
                break

    #안익은 토마토가 최소 한개라도 있다면..
    if cnt_green>=1:
        #모든 토마토가 익을때 까지 걸리는 시간(일)
        #2. 안익은 토마토가 있다면
        #방문하지 않은 상태인, 익은 토마토를 찾는다.
        for y in range(N):
            for x in range(M):
                if (tomatoes[y][x]==1) and (not visited[y][x]):
                    #일단 큐에 넣는다.
                    q.append((y,x,0))
                    
        #bfs를 실행한다
        day=bfs()
        #3. 아직도 안익은 토마토가 존재한다면?
        for y in range(N):
            for x in range(M):
                if tomatoes[y][x]==0:
                    day=-1
                    break
    print(day)

if __name__=='__main__':
    main()