[백준알고리즘] 7576번: 토마토 -Python

[백준알고리즘] 7576번: 토마토 -Python

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

7576번: 토마토

시간 초과 때문에 고생을 조금 했던 문제이다. 우선은 시간을 줄인 부분을 빼고 다른 부분들을 먼저 보겠다.

 

토마토의 배치에 대한 입력을 받고, BFS 방식으로 모든 토마토가 익는 최소 일수를 구해주었다. BFS는 3번째 예제에서 알 수 있듯이 토마토가 있는 하나에서 시작되는 방식이 아니다. 익은 토마토가 처음에 두 개라면 두 개에서 동시에 익기 시작해야 한다. 

 

그리고 모든 토마토가 각자 자신이 익을 수 있는 최소 일수를 갖도록 했다. 마지막에 토마토 중에서 0을 갖고 있는 토마토는 안 익은 것이기 때문에 모든 토마토가 익을 수 없는 상태라는 것으로 출력하고, 0이 없다면 그중에서 마지막 토마토가 익는 일수를 구하기 위해서 최댓값을 구한다.

 

여기서 내가 시간을 줄인 곳은 두 곳이다.

 

우선 첫 번째로 위에서 말했듯이 익은 토마토가 두 개 이상일 때 하나의 토마토에서만 시작을 하게 된다면, 모든 토마토가 익는 최소 일수를 구하는 것이 아니게 된다. 따라서 초기에 익어있는 토마토에서는 모두 시작을 해야 한다. 하지만 초반에는 처음 익어있던 토마토 중 하나에서 시작을 하고, 그다음 처음 익어있던 다른 토마토에서 또 일수를 구하면서 각 토마토는 최솟값을 갱신하도록 했다. 예를 들어서 아래처럼 2개의 익은 토마토와 3개의 안 익은 토마토가 있다고 했을 때 다음과 같이 했었다.

    1 0 0 0 1

-> 1 2 3 4 1 # 왼쪽 1에서부터 시작 (4번의 이동)

-> 1 2 3 2 1 # 오른쪽 1에서부터 덮어쓰기 시작 (4번의 이동 및 비교)

 

이런 식으로 하게 되면 쓸데없이 덮어쓰는 과정 동안 방문했던 위치를 한 번 더 방문하게 되는 것이다. 또한 BFS는 한 번 방문하면 끝인 알고리즘인 것을 고려해서 처음에 익어있는 모든 토마토에서부터 시작을 하도록 했다. 위에서는 모든 반복문을 적지 않았지만 여기서는 확인해보도록 하겠다. 같은 배치의 토마토가 존재한다고 했을 때  다음과 같이 처리하는 것이다.

    1 0 0 0 1

-> 1 2 0 0 1 # 0번 인덱스에 위치한 왼쪽 1에서 갈 수 있는 1번 인덱스의 값 변경

-> 1 2 0 2 1 # 4번 인덱스에 위치한 오른쪽 1에서 갈 수 있는 3번 인덱스의 값 변경

-> 1 2 3 2 1 # 1번 인덱스에 위치한 값에서 갈 수 있는 2번 인덱스의 값 변경

 

이렇게 처리하기 위해서는 반복문으로 모든 리스트를 찾아서 1의 위치를 찾는 것은 비효율적일 것이다. 또한 초기에 BFS 큐에 넣어주어야 하기 때문에두 번째시간을 줄인 방법이 나오게 되었다.

 

방법은 초기에 입력을 받을 때 바로 BFS에 사용할 큐에 넣은 것이다. 이렇게 함으로써 1을 찾기 위해서 이중 for문을 한 번 더 써서 O(N^2)이라는 시간을 더 사용하지 않아도 되게 된 것이다.

 

그 외에는 일반적인 BFS문제처럼 BFS로 상하좌우의 값을 비교해서 갱신 가능한지 확인했다.

 

import sys
from collections import deque

def bfs():
    global box
    while queue:
        qi, qj, d = queue.popleft()
        if not 0<qi<=n or not 0<qj<=m or box[qi][qj] != 0:
            continue

        box[qi][qj] = d
        d += 1
        queue.append((qi-1, qj, d))
        queue.append((qi, qj-1, d))
        queue.append((qi, qj+1, d))
        queue.append((qi+1, qj, d))

m, n = map(int, sys.stdin.readline().split())
box = [0]
queue = deque()
for i in range(1, n+1):
    t = list(map(int, sys.stdin.readline().split()))
    box.append([-1] + t)
    for j in range(1, m+1):
        if box[i][j] == 1:
            queue.append((i, j, 1))
            box[i][j] = 0
days = 0

# find minimum days
bfs()

# print minimum days
for bl in box[1:]:
    for b in bl:
        if b == 0:
            days = -1
            sys.stdout.write(str(-1))
            exit()
        days = max(days, b-1)
sys.stdout.write(str(days))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다