7576번: 토마토

본 글의 내용은 절대적으로 좋은 코드라는 보장이 없습니다. 글을 읽어보시다가 "이 사람은 이런 식으로 짰구나. 되게 허접하게 짰네?" 라는 생각이 드시면 댓글을 통해서 좋은 가르침과 의견을 주시면 감사합니다!!

---

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

7576번: 토마토

 

기본 아이디어

• 날이 지날 때마다 익은 토마토에서 안 익은 토마토로 번져나가는 구도가 BFS에 가깝다고 생각하여 BFS로 구현하였다.
• 큐(Queue)에는 익은 토마토의 x좌표, y좌표와 익은 날에 대한 정보를 담아주었다.
• 익은 날이 갱신될 때마다 기록해주었다.
• 처음 익지 않은 토마토의 개수를 기록해 놓고 익을 때마다 익지 않은 토마토의 개수를 1씩 감소시켜준다.
• 익는 과정이 끝났는데도 익지 않은 토마토의 개수가 0이 아니라면 -1을 출력한다.

import sys
sys.stdin = open('input.txt', 'r')
from collections import deque

M, N = map(int, input().split())
box = []
for n in range(N):
    box.append(list(map(int, input().split())))

Q = deque([])

zeroCount = 0

for n in range(N):
    for m in range(M):
        if box[n][m] == 1:
            Q.append([m, n, 0])
        elif box[n][m] == 0:
            zeroCount += 1

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

min_day = 0

while Q:
    v = Q.popleft()

    for d in range(4):
        new_x = v[0] + dx[d]
        new_y = v[1] + dy[d]
        if -1 < new_x < M and -1 < new_y < N and not box[new_y][new_x]:
            box[new_y][new_x] = 1
            new_day = v[2] + 1
            zeroCount -= 1
            Q.append([new_x, new_y, new_day])
            if new_day > min_day:
                min_day = new_day

if zeroCount == 0:
    print(min_day)
else:
    print(-1)

 

유의사항

• 일반적인 리스트로 큐를 구현할 경우 시간 초과가 나와 동작하지 않았다. 따라서 sys의 collections에서 deque를 가져와 deque를 통해 BFS를 수행하였다.