백준 토마토(7576) - 골드 Ⅴ

문제 링크

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

문제 분석

• 이 문제가 BFS 문제인 이유
  • 각 격자 칸들이 상하좌우로 움직이면서 서로를 오갈 수 있음 → 그래프 표현 가능
  • 특정한 격자에서 시작해 상하좌우로 움직이면서 각 격자에 도달해야 함 → 그래프 탐색
  • 상하좌우로 움직일 때 격자 간의 거리가 모두 동일하고, 최단 거리(경로, 비용 …)를 찾아야 함
    • 거리가 동일하다는 조건이 없으면 BFS로는 못 구하고 다른 알고리즘(다익스트라, 벨만포드 등등)으로 구해야 함

부연 설명

• BFS는 vertex 간의 edge의 길이가 모두 동일할 때 최단 거리(경로)를 보장한다.
  • 시작점이 여러 개라도 마찬가지
  • DFS는 최단 거리가 아닐 수 있음
    • 밑의 예시를 보면 A -> C 에서 BFS는 그 원리상 거리 1로 경로를 찾지만, DFS는 탐색 순서에 따라 다른 결과가 나올 수 있음

아이디어

• 익은 토마토들에서 시작해서 BFS하자 → 그러면 모든 토마토까지 최단 거리를 알 수 있음

  3	4	-1
  2	-1	3	-1
  1	-1	2	1
  0	1	1	0

• 만약에 최단 거리가 없는 토마토가 있으면 안 익는 토마토가 있으니 -1 반환하고,
  아니면 최단 거리들 중에 최대값을 반환하자
• 의사 코드

  
  graph <- 위의 토마토 창고
  ripes <- 익은 토마토들 위치
  
  queue <- BFS용 큐
  for ripe in ripes : queue.append(ripe) # 익은 토마토들 위치 초기값으로 넣음
  
  while queue:
  		x, y = queue.popleft()
  		
  		for new_x, new_y in ... <- 상하좌우 이동한 위치
  				if graph[new_x][new_y] == 0:
  						graph[new_x][new_y] = graph[x][y] + 1 # visited + distance
  						queue.append((new_x, new_y))
  
  if 0 in graph : return -1
  else : return max(graph)
  		

코드

from collections import deque
import sys

class Graph:
  def __init__(self, w:int, h:int):
    self.w = w
    self.h = h 
    self.graph = []
    self.queue = deque()
		self.cnt_tomato = 0

    for _ in range(h):
        inp = list(map(int, sys.stdin.readline().split()))

        for i, v in enumerate(inp):
          if v == 1 : self.queue.append((_, i))
					if v == 0 : self.cnt_tomato += 1
        self.graph.append(inp)
    
  def BFS(self):
    if len(self.queue) == 0 : return -1
		result = 0

    while self.queue:
      x, y = self.queue.popleft()

      k1 = [1, 0, -1, 0]
      k2 = [0, 1, 0, -1]

      for i in range(4):
        new_x = x + k1[i]
        new_y = y + k2[i]

        if 0<=new_x<self.h and 0<=new_y<self.w and self.graph[new_x][new_y] == 0:
          self.graph[new_x][new_y] = self.graph[x][y] + 1

					result = max(self.graph[x][y] + 1, result)
					self.cnt_tomato -= 1

          self.queue.append((new_x, new_y))

    if self.cnt_tomato != 0: return -1
		else: return result

W, H = map(int, sys.stdin.readline().split())

graph = Graph(W, H)
answer = graph.BFS()
print(answer)