[Python] 백준 7576번 : 토마토 (S1) - DFS&BFS단계별6

#문제

www.acmicpc.net/problem/7576

7576번: 토마토

#풀이 & 학습한 내용

"BFS로 토마토를 익히는 문제"입니다. bfs를 시작하기 전에 익은 토마토들을 먼저 모두 큐에 넣고 수행하는 것이 핵심입니다. 그리고 bfs가 끝나고 큐가 모두 비워지면 익을 수 있는 토마토는 모두 익은 것이므로, bfs이후에 안익은 토마토가 있는 지 확인하여 모두 익히는 것이 불가능한지 여부를 확인해주면 됩니다.

 

#소스코드

from collections import deque #큐 사용하기 위해 import

def bfs(q):
  while q: #큐가 빌때까지 반복(큐가 비었다는건 익을 수 있는애들은 다 익었다는 의미)
    v = q.popleft() #큐에서 하나 꺼내기
    nowX = v[0]
    nowY = v[1]
    count = v[2] #큐에서 꺼낸거까지의 지난 일수
    for i in range(4): #상하좌우 방향
      newX = nowX + dx[i]
      newY = nowY + dy[i]
      if (0 <= newX < N) and (0 <= newY < M):
        if tomatoes[newX][newY] == 0 and tomatoes[newX][newY] != -1:
          tomatoes[newX][newY] = 1 #익음처리
          q.append([newX, newY, count + 1]) #날짜 하나 더 지난 상태로 큐에 추가
  return count #큐에서 마지막으로 꺼내진거의 지난 일수(모든 토마토 익었으면 답)

def check(answer,tomatoes):
  for i in range(len(tomatoes)):
    for j in range(len(tomatoes[i])):
      if tomatoes[i][j] == 0: #익지 않은게 있다면
        return -1
  return answer

M,N = map(int,input().split())
tomatoes = [list(map(int,input().split()))for _ in range(N)] #2차원 리스트 입력받기

dx=[0,0,1,-1]
dy=[1,-1,0,0]
q=deque([]) #큐 초기화

for i in range(len(tomatoes)):
  for j in range(len(tomatoes[i])):
    if tomatoes[i][j] == 1:
      q.append([i,j,0]) #★bfs시작전에 익은 토마토 큐에 모두 넣어주기

answer = bfs(q)
print(check(answer,tomatoes))

 

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_7576.py

HoYoungChun/Algorithm_PS

다음 글을 많이 참조했습니다 velog.io/@devjuun_s/%ED%86%A0%EB%A7%88%ED%86%A0-%EB%B0%B1%EC%A4%80-7576%EB%B2%88python

토마토-백준 7576번(python)