백준 7576 - 파이썬

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

7576번: 토마토

문제 풀이

이번 문제 역시 기본적인 BFS 틀을 활용하여 푸는 문제였다. 처음에 여러가지 시도를 하였다. 토마토가 총 몇개 익을지는 이전 문제들에서 푼 방식을 적용하여 풀면 되었는데, 토마토가 익는데는 하루가 걸리는데 이 하루를 어떻게 묶을지가 어려웠다. 고민 끝에 찾아낸 규칙은 큐가 들어가고 나서 상하좌우를 탐색하는 동안 처음 큐에서 나온 x와 y의 값은 동일하다는 점이다. 이 점을 활용하여 주변에 탐색되는 값들에 1을 더하면 총 몇일에 걸쳐 익었는지 알 수 있다.

 

import sys
from collections import deque

def bfs(graph, x, y):
  q = deque()
  q.append((x, y))

  dx = [-1, 1, 0, 0,]
  dy = [0, 0, -1, 1]

  while q:
    x, y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue

      if graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1
        q.append((nx, ny))


m, n = map(int, input().split())
res = 0

graph = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      bfs(graph, i, j)

for i in graph:
  for j in i:
    if j == 0:
      print(-1)
      exit(0)
  res = max(res, max(i))

print(res -1)

하지만 위 코드는 오답처리 되었다. 원인을 찾다가 해결하지 못하고 다른 사람의 풀이를 찾아보았다.

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])

bfs()
for i in graph:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)

이 사람의 코드를 살펴보면 가장 처음 찾은 1의 위치를 큐에 추가하였고, 그 뒤에는 추가하지 않았다. 이 점이 나의 코드와 다른 점이다. 나는 1을 찾을때마다 bfs함수를 새롭게 호출하였기 때문에 계산이 중복되었던 것이다. 정말 사소한 부분이지만 다른 점인거 같다.

 

이번 문제를 풀면서 느낀 점은 아직 문제를 활용하고 디테일한 부분을 코드로 표현하는 것이 어려운거 같다. 결국, 많이 생각하고 많이 풀어보면서 유형을 익히는 수밖에 없는거 같다.