[DFS/BFS/완전탐색] ▲ 7576번 - 토마토(BFS)

[백준] 7576번 - 토마토

풀이 시간: 40분 이내

 

1) 문제 해결 아이디어

토마토가 모두 익을 때까지 최소 날짜를 구하는 문제다.

익은 토마토가 상하좌우로 인접한 위치에 있는 익지 않은 토마토를 익힌다.

지금껏 풀어왔던 최단 경로 문제와 비슷하며 이 문제는 BFS로 풀어야 한다.

 

이 문제에서 3가지 케이스가 있다.

1. 저장될 때부터 모든 토마토가 익어있는 경우(즉, 입력받은 2차원 리스트에 0인 값이 없다면)

-> 0 출력

2. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익지 못하는 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나라도 있으면)

-> -1 출력

3. 토마토가 익는 과정이 모두 끝난 후 토마토가 모두 익었을 경우(즉, bfs 수행 후 2차원 리스트에 0인 값이 하나도 없으면)

-> 최소 날짜 출력

 

이 문제가 다른 BFS 문제들과 약간 다른 점이 있다면 그래프 시작 좌표가 여러개 있을 수 있다는 점이다.

보통의 BFS 문제는 2차원 리스트를 for문을 돌면서 특정값을 찾으면 그 좌표를 시작점으로 하여 bfs()를 호출하는 형태로 구현한다. 하지만 이 문제는 1개 이상인 익은 토마토가 동시에 상하좌우로 탐색하는 과정이 필요하기 때문에 기존 처럼 특정값을 찾으면 바로 bfs()를 호출하는 것이 아니라 익은 토마토 좌표들을 리스트로 매개변수로 넘겨 bfs()를 호출해주어야 한다.

 

토마토가 모두 익을 때까지 최소 날짜는 (graph의 최댓값 - 1)이 된다. 

Q. 최댓값에서 1을 빼는 이유는?

실제로 1과 인접한 위치에 2를 기록하지만 2를 기록하기 까지 걸린 시간은 2일이 아니라 1일이기 때문에 실제로 기록된 값에서 1을 빼준 값이 최소 날짜가 된다.

 

2) 소스코드

from collections import deque

m, n = map(int, input().split())  # 가로, 세로
# 1: 익은 토마토, 0: 익지 않은 토마토, -1: 빈 칸
graph = [list(map(int, input().split())) for _ in range(n)]
target = []  # 익은 토마토 좌표들
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS
def bfs(target):
  # 익은 토마토가 있는 모든 좌표 삽입
  queue = deque() 
  for i in target:
    queue.append(i)

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

      # 범위 내이고 익지 않은 토마토(0)이라면
      if(0 <= nx < n and 0 <= ny < m):
        if(graph[nx][ny] == 0):
          # 삽입, 방문 처리
          queue.append((nx, ny))
          graph[nx][ny] = graph[x][y] + 1  # 익은 토마토로 변환

# 1. 저장될 때 부터 모든 토마토가 익었다면(입력받은 값 중 0이 없다면)
if all(0 not in l for l in graph):
  print(0)
# 안익은 토마토가 하나라도 있다면
else:
  # 익은 토마토 좌표 구하기
  for i in range(n):
    for j in range(m):
      if(graph[i][j] == 1):
        target.append((i, j))
  # 익은 토마토들에 대해 bfs 수행
  bfs(target)
  # 2.토마토가 모두 익지 않았다면(0인 값이 1개라도 있으면)
  if any(0 in l for l in graph):
    print(-1)
  # 3. 토마토가 모두 익었다면(0인 값이 없다면)
  else:
    # 최댓값 출력()
    print(max(map(max, graph)) - 1)

 

<2차원 리스트에서 원소 포함 여부 검사>

# 10*10 2차원 리스트
graph = [[0] * 10 for _ in range(10)]	

all(0 not in l for l in graph)	# 0인 원소가 하나도 없으면 True
any(0 in l for l in graph)		# 0인 원소가 하나라도 있으면 True

all(반복 자료형)	인자로 받은 데이터의 모든 요소가 True일 때 True 반환 인자로 받은 요소가 비어있으면 True반환
any(반복 자료형)	인자로 받은 데이터의 요소가 하나라도 True일 때 True 반환 인자로 받은 요소가 비어있으면 False반환

[참고] https://velog.io/@woo0_hooo/python-2%EC%B0%A8%EC%9B%90-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%90%EC%84%9C-%EC%9B%90%EC%86%8C%EC%9D%98-%ED%8F%AC%ED%95%A8%EC%97%AC%EB%B6%80-%EA%B2%80%EC%82%AC%ED%95%98%EA%B8%B0

[python] 2차원 리스트에서 원소의 포함여부 검사하기

[참고] https://blockdmask.tistory.com/430

[python] 파이썬 all, any 함수 정리 및 예제

 

<2차원 리스트 최댓값, 최솟값 찾기>

max(map(max, graph))	# graph의 최댓값
min(map(min, graph))	# graph의 최솟값

[참고] https://devbull.xyz/python-2caweon-baeyeolyi-coedaegabs-coesogabs-cajgi/

Python 2차원 배열의 최대값, 최소값 찾기