파이썬 알고리즘 069 | 토마토(BFS 활용)

69. 토마토(BFS 활용)

현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림
과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수
있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은
토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향
에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토
가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나
면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들
의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로
그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
▣ 입력설명
첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N
은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000 이다.
둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄
에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토
의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수
-1은 토마토가 들어있지 않은 칸을 나타낸다.
▣ 출력설명
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든
토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을
출력해야 한다.

▣ 입력예제 1
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
▣ 출력예제 1
4
출처 : 한국정보올림피아드

<내 풀이>

일단 여기까지 했는데, index out of range가 자꾸 뜬다ㅠㅠ 원인이 무엇일까..
====>n이 열이고 m이 행이었다...

m,n =map(int,input().split())
a=[list(map(int, input().split())) for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
cnt=0
for i in range(m):
    for j in range(n):
        q.append((i,j))
        while q :
            cnt+=1
            k=q.popleft()
            for i in range(4) :
                xx=k[0]+dx[i]
                yy=k[1]+dy[i]
                if 0<=xx<m and 0<=yy<n and a[xx][yy]==0:
                    a[xx][yy]=1
                    q.append((xx,yy))
                
        
print(cnt)

(2) 입력값 수정하고
==>근데 cnt로 날짜구하려고 했는데, 잘못된 접근이었다
===>왜냐하면 pop할 때마다 세면, 순서를 다 다르게 보는건데
동시적으로 일어나는 순간도 존재함. pop으로 계산하면 이를 누락하는 것
====>dis라는 [0]]리스트 만들어서 pop되는 부모q에 1을 더해주면, 동시적으로 일어나는 순간도 고려할 수 있게 됨

n,m =map(int,input().split())
a=[list(map(int, input().split())) for _ in range(m)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
cnt=0
for i in range(m):`
    for j in range(n):
        q.append((i,j))
        cnt+=1
while q :
    k=q.popleft()
    for h in range(4) :
        xx=k[0]+dx[h]
        yy=k[1]+dy[h]
        if 0<=xx<m and 0<=yy<n and a[xx][yy]==0:
            a[xx][yy]=1
            q.append((xx,yy))
            

(3) 풀이를 참고해서 구현한 최종 풀이

from collections import deque
n,m =map(int,input().split())
a=[list(map(int, input().split())) for _ in range(m)]
num=[[0]*n for _ in range(m)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
cnt=0
for i in range(m):
    for j in range(n):
        if a[i][j]==1:
            q.append((i,j))
while q :
    k=q.popleft()
    for h in range(4) :
        xx=k[0]+dx[h]
        yy=k[1]+dy[h]
        if 0<=xx<m and 0<=yy<n and a[xx][yy]==0:
            a[xx][yy]=1
            num[xx][yy]=num[k[0]][k[1]]+1
            q.append((xx,yy))

flag=1
for i in range(m):
    for j in range(n):
        if a[i][j]==0:
            flag=0
if flag==1:
    print(max(map(max,num)))
else :
    print(-1)

<풀이>

• 익은 토마토가 언제 익었는지 날짜 넣어줄 2차원 리스트 만들어놓기

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
n, m=map(int, input().split())
board=[list(map(int, input().split())) for _ in range(m)]
Q=deque()
dis=[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        if board[i][j]==1:
            Q.append((i, j))
while Q:
    x, y=Q.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx<m and 0<=ny<n and board[nx][ny]==0:
            board[nx][ny]=1
            dis[nx][ny]=dis[x][y]+1
            Q.append((nx, ny))
flag=1
for i in range(m):
    for j in range(n):
        if board[i][j]==0:
            flag=0
result=0
if flag==1:
    for i in range(m):
        for j in range(n):
            if dis[i][j]>result:
                result=dis[i][j]
    print(result)
else:
    print(-1)

<반성점>

• ===>왜냐하면 pop할 때마다 세면, 순서를 다 다르게 보는건데
  동시적으로 일어나는 순간도 존재함. pop으로 계산하면 이를 누락하는 것
  ====>dis라는 [0]]리스트 만들어서 pop되는 부모q에 1을 더해주면, 동시적으로 일어나는 순간도 고려할 수 있게 됨

<배운 점>

-토마토가 다 익지 못하는 경우 판별 : flag 설정해주는 것
: flag=1과 같이 설정해놓고 마무리된 2차리스트 a를 탐색하다 익지 않은 토마토 발견한다면(0) flag=0이라고 설정해주기만 하면 된다
그리고 다음에 if flag==0 / else : 로 나누어서 원하는 값 출력하면 됨

<2회독 내 풀이>

• 행이랑 열 계속 주의하기 a[열][행]이다

from collections import deque
m,n = map(int,input().split()) #m이 열 n이 행
a=[list(map(int,input().split())) for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
for i in range(n) :
    for j in range(m) :
        if a[i][j]==1:
            q.append((i,j,0))
while q:
    k=q.popleft()
    for i in range(4) :
        xx=k[0]+dx[i]
        yy=k[1]+dy[i]
        if 0<=xx<n and 0<=yy<m and a[xx][yy]==0:
            a[xx][yy]=1
            kk=k[2]+1
            q.append((xx,yy,kk))
print(kk)