[백준 7576] 토마토 (Python)

👩🏻‍💻문제링크

[백준 7576] 토마토 (Python)

✍️Idea Sketch

2021-08-02

1. 예상 출력값

1) 처음부터 모두 익은 경우, 즉 입력값에 0이 없는 경우에는 0을 출력한다.
2) 0이 모두 1이 되기까지 걸리는 최소 날짜를 출력한다.
3) 모두 익지는 못하는 경우, 즉 모든 연산이 끝난 후에도 0이 남아있는 경우에는 -1을 출력한다.

2. main 로직

• 입력값을 받아 graph 에 정리한다.
• 익은 토마토의 x, y 인덱스를 queue에 저장한다.
• queue의 첫번째 요소 x, y를 pop한다.
• dfs 연산을 하기 위해 방문여부를 초기화한다. (visited[y][x] = 0)
• dfs(x, y) 함수를 호출한다.

3. DFS 로직

• 경계값을 분석한다.
• 처음 방문하면서
  1) 익은 토마토일 경우, 상하좌우 인접한 곳에 있는 토마토에게 영향을 끼친다.
  2) 익지 않는 토마토일 경우 익으며, 이 토마토의 x, y 인덱스를 queue에 추가한다.

✍️소스코드

2021-08-02 3528ms 통과

• 더 효율적인 로직 존재

from collections import deque
import sys
sys.setrecursionlimit(10**6)

def dfs(x, y):
  if (0<=x<m) and (0<=y<n) and visited[y][x] == 0:
    visited[y][x] = 1
    if graph[y][x] == 1:
      dfs(x, y-1)
      dfs(x, y+1)
      dfs(x-1, y)
      dfs(x+1, y)
    if graph[y][x] == 0:
      graph[y][x] = 1
      queue_x.append(x)
      queue_y.append(y)
    return True

if __name__ == "__main__":
  m, n = map(int, input().split())
  graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
  visited = [[0 for _ in range(m)] for _ in range(n)]

  queue_x = deque([])
  queue_y = deque([])
  flag_0 = False 

  for i in range(n):
    if 1 in graph[i]:  
      for j in range(m):
        if graph[i][j] == 1:
          queue_x.append(j)
          queue_y.append(i)
    if 0 in graph[i]:
      flag_0 = True

  if flag_0 == False:  #1 : 처음부터 0이 하나도 없는 경우
    print(0)
    sys.exit(0)

  result = 0  #2 : 0이 모두 1이 되기까지 최소 소요 날짜
  while len(queue_x) != 0:
    l = len(queue_x)
    for _ in range(l):
      x = queue_x.popleft()
      y = queue_y.popleft()
      visited[y][x] = 0
      dfs(x, y)
    result += 1

  for i in graph:  #3 : 연산 후에도 0이 남아있는 경우
    if 0 in i:
      print(-1)
      sys.exit(0)

  print(result-1)