[백준] 7576번: 토마토

문제

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

풀이

import sys
from collections import deque

answer = 0
M, N = map(int, sys.stdin.readline().split(" "))
remain = N * M
box = []
q = deque()
visited = [[False] * M for _ in range(N)]
for i in range(N):
    row = list(map(int, sys.stdin.readline().split(" ")))
    box.append(row)

    for k in range(M):
        if row[k] == 1:
            q.append((i, k, 0))
            visited[i][k] = True
            remain -= 1
        if row[k] == -1:
            remain -= 1

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

while q:
    cur_y, cur_x, days = q.popleft()
    for i in range(4):
        next_y = cur_y + dy[i]
        next_x = cur_x + dx[i]
        if 0 <= next_y < N and 0 <= next_x < M and box[next_y][next_x] != -1 and not visited[next_y][next_x]:
            q.append((next_y, next_x, days + 1))
            remain -= 1
            visited[next_y][next_x] = True
            answer = max(answer, days + 1)

if remain:
    print(-1)
else:
    print(answer)

BFS를 활용한 풀이.
주어진 모든 토마토의 좌표값을 deque에 넣고 bfs를 시작한다.

deque에 append할 수 있는 조건은 다음과 같다.
1. 현재 토마토 좌표값으로부터 상하좌우의 범위가 유효하다.
2. 방문한 적이 없다.

조건이 모두 만족하면 deque에 넣는다.
남은 토마토의 개수(remain)을 1 감소시킨다.
deque에 넣는 즉시 방문처리한다.
현재 answer 값과 날짜 수를 비교하여 더 큰 값을 answer에 재할당 한다.

만약 남아있는 토마토가 있다면 -1를 출력하고
그렇지 않다면 answer 값을 출력한다.