백준 7576번(토마토) 파이썬

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

7576번: 토마토

이 문제는 수월하게 가다가 "예제 입력 3" 조건에서 막혔다. 1이 2개가 있어서 이거를 차례대로 번갈아가면서 수행을 해줘야 하는데 어떻게 해야하지 고민을 오래했다. 그러다 bfs의 특징인 deque의 특징이 생각났다. 

큐의 특징은 FIFO(first-in-first-out)이다. 즉, 내가 원하는 차례대로 번갈아가면서 수행이 가능하단 것이다. 

지금까지는 bfs문제에서 큐 삽입을 bfs() 함수 안에서 해주었지만 이 문제 같은경우 2개이상을 삽입해야하는 경우도 있기 때문에 함수 밖에서 먼저! 익은 토마토에 대한 삽입을 먼저 해주었다. 그 이후는 다른 문제들고 크게 다른게 없다.

아래 코드의 주석에 설명을 달아놓았다.

import sys
from collections import deque

input = sys.stdin.readline

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

graph = []
visited = [[0]*M for _ in range(N)]
q=deque() # 데크 선언

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

for _ in range (N):
    graph.append(list(map(int,input().split()))) # 그래프 입력 받기
    
                
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1: # 토마토가 익은 위치를 데크에 삽입
            q.append((i,j))
            
def bfs():
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if(0<=nx<N and 0<=ny<M and graph[nx][ny] == 0):
                q.append((nx,ny))
                graph[nx][ny] = graph[x][y]+1 # 현위치에서 이동할때마다 1씩 더해준다
                
bfs() # bfs 실행

count = 0 # 익을 수 업는 토마토의 갯수를 가운트 해줄 변수

for i in range (N): # bfs문이 실행되고나서 익지 못하는 토마토를 찾아 count++ 해준다
    for j in range (M):
        if graph[i][j] == 0:
            count+=1
            
if count == 0: # 익지 못한 토마토가 없을경우
    print(max(map(max,graph))-1)# 그래프에서 최대값을 찾아 -1을 해준다
                                # -1을 해주는 이유는 시작하는 부분은 빼야하기 때문이다.
else: # 익지 못한 토마토가 있을경우
    print(-1)

큐의 특징에 대해 다시한번 짚고 넘어가는 계기가 되는 문제였다.

좋은 문제인 거 같다.