[백준] python 7576번 토마토

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

7576번: 토마토

문제 설명은 위와 같다.

 

문제를 보고 맨 처음엔 BFS를 이용해서 풀어야겠구나 생각을 했지만 어떻게 풀어야 할 지는 몰랐다. 

우선 시작점이 하나가 아니라 여러 곳에서 시작하고 일수는 어떻게 재야할지 알아내지 못했다.

그래서 일단 풀어보자는 생각으로 풀었다. 틀렸지만

 

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

tomato = []
day = 0
move = True
for i in range(n):
    tomato.append(list(map(int, input().split())))
prev = tomato.copy()
while move:
    day += 1
    move = False
    for i in range(n):
        for j in range(m):
            if (prev[i][j] == 1):
                if (i+1 < n and prev[i+1][j] == 0):
                    move = True
                    tomato[i+1][j] = 1
                if (i-1 >= 0 and prev[i-1][j] == 0):
                    move = True
                    tomato[i-1][j] = 1
                if (j+1 < n and prev[i][j+1] == 0):
                    move = True
                    tomato[i][j+1] = 1
                if (j-1 >= 0 and prev[i][j-1] == 0):
                    move = True
                    tomato[i][j-1] = 1
    prev = prev.copy()
print(day)

일단 여기서 발생한 문제는 기존 배열값이 복사가 안된다... 하나씩 다 돌아보면서 하나라도 주변에 안익은 토마토가 있고 이전 값에도 익었던 토마토여야 작동하는 함수로 하나라도 바뀔 게 있으면 while문을 계속 도는 걸 생각했다. 근데 내 예상과는 다르게 동작했다.. 그래서 실패..

https://jae04099.tistory.com/entry/%EB%B0%B1%EC%A4%80-7576-%ED%86%A0%EB%A7%88%ED%86%A0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%B4%EC%84%A4%ED%8F%AC%ED%95%A8

이 불로그 내용을 참고해서 다시 코드를 짰다.

from collections import deque

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

tomato = []
queue = deque()
for i in range(n):
    tomato.append(list(map(int, input().split())))
for i in range(n):
    for j in range(m):
        if (tomato[i][j] == 1):
            queue.append([i, j])
while queue:
    x, y = queue.popleft()
    xm = [1, -1, 0, 0]
    ym = [0, 0, 1, -1]
    for i in range(4):
        nx = x + xm[i]
        ny = y + ym[i]
        if (0 <= nx < n and 0 <= ny < m and tomato[nx][ny] == 0):
            tomato[nx][ny] = tomato[x][y]+1
            queue.append([nx, ny])
result = 0
for i in range(n):
    for j in range(m):
        if (tomato[i][j] == 0):
            print(-1)
            exit(0)
    result = max(result, max(tomato[i]))
print(result-1)

bfs를 이용하고 처음에 1인 토마토를 전부 큐에 넣는다. 그리고 하나씩 꺼내면서 주위에 덜익은 토마토가 있을 때 그 덜익은 토마토를 익은 토마토로 바꾸면서 +1을 해서 넣는 방식이었다. 와 이걸.. 나는 왜 이걸 생각 못했나 자괴감이 약간 든다.. 아직 bfs와 dfs에 대해 잘 모르는 것 같다..