[백준 7576] 토마토(파이썬)

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

7576번: 토마토

전형적인 BFS를 이용한 풀이입니다.

이런 유형의 문제는

풀이방법을 모른다면

체감난이도가 확 올라갈 수 있습니다.

그 이유는

'최소일수'를 구하는 것 때문이죠.

이 문제를 BFS로 푼다,

아니면 하다못해 DFS로 푼다는 것까지는

문제 유형을 읽다보면 생각이 어느정도 납니다.

'토마토가 익을 때는

인접한 왼쪽 오른쪽만 익히는 구나.

그럼 토마토가 익는 걸 기점으로

그래프를 이동시키면 되겠네'

여기서 최소일수를 구하는 부분이 난감해집니다.

평소 DFS,BFS를 풀 때, deque에 넣고 푸는 건 아는데

최소일수는 어떻게 구하지??

저는 우선 visited리스트를

-1로 전부 초기화했습니다.

그리고 토마토가 있는 부분은 0

토마토가 없는 부분은 -2로 표시했습니다.

-1은 현재 토마토가 있지만

익지 않았다는 의미.

이후 BFS를 시도하면서

길찾아가면서 하나씩 위로 카운트해줍니다.

그 다음, 리스트에서

각 열의 최댓값을 찾아서 출력합니다.

그 때, 리스트에 -1이 남아있으면

'안 익은 토마토가 있다'라는 의미이므로

-1을 출력해줍니다.

 

아래는 제가 풀었던 코드입니다.

#백준 7576 토마토
from collections import deque

M,N=map(int,input().split())

dx=[0,0,1,-1]
dy=[1,-1,0,0]
#1. 토마토를 입력받음
room=[]
no=[]
tomato=deque()

visited=[[-1]*M for _ in range(N)]

for i in range(N):
    data=list(map(int,input().split()))
    for j in range(M):
        if data[j]==1:
            tomato.append([i,j])
            visited[i][j]=0
        elif data[j]==-1:
            visited[i][j]=-2

    room.append(data)


#2 토마토가 익는지 볼 것.

while tomato:
    x,y=tomato.popleft()
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue
        if not visited[nx][ny]==-1:
            continue

        tomato.append([nx,ny])
        visited[nx][ny]=visited[x][y]+1


answer=0
not_in=0
for i in range(N):
    m=max(visited[i])
    answer=max(answer,m)
    if visited[i].count(-1):
        not_in=1

if not_in==1:
    print(-1)
else:
    print(answer)

https://jiwon-coding.tistory.com/97

[백준] 7576번 토마토 / 파이썬(python)

https://jae04099.tistory.com/entry/%EB%B0%B1%EC%A4%80-7576-%ED%86%A0%EB%A7%88%ED%86%A0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%B4%EC%84%A4%ED%8F%AC%ED%95%A8

[백준] 7576: 토마토 (파이썬 / 해설포함)

참고 코드까지 참고하셔서

공부에 도움이 되셨으면 좋겠습니다.