7576 토마토

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from collections import deque
import sys
read = sys.stdin.readline

M,N = map(int,read().split())
graph = []
for _ in range(N):
    array = list(map(int,read().split()))
    graph.append(array)

dx = [0 , 0 , -1 , 1] # 상 하 좌 우
dy = [-1, 1, 0, 0] # 상 하 좌 우


# 한번 싹 훑으면서 토마토가 익은 것을 다 찾아서 queue에 넣자.
q = deque()
for y in range(N):
    for x in range(M):
        if graph[y][x] == 1 :
            q.append([y,x])

# 함수 쓰지 말고 그냥 전개하자 어차피 반복문일뿐.
days = 0
while q:
    days += 1
    # print("days : {}".format(days))

    for qq in range(len(q)):
        now = q.popleft()
        for j in range(4):
            ny = now[0] + dy[j]
            nx = now[1] + dx[j]

            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue

            if graph[ny][nx] == 0:  # 주변에 토마토가 안있었으면
                # 토마토를 익게하고 queue에 넣자
                graph[ny][nx] = 1
                # visited[ny][nx] = 1
                q.append([ny, nx])
    #
    # print(q)
    # for f in range(N):
    #     print(graph[f])
    # print()

check_zero = False
for y in range(N):
    for x in range(M):
        if graph[y][x] == 0:
            check_zero = True
if check_zero :
    print(-1)
else :
    print(days-1)

3. 문제 풀이

이 문제는 BFS를 활용할 수 있는지에 물음과 동시에 조금 변형된 문제이다. 왜냐하면 토마토가 한곳에서만 시작하는게 아닌, 다른 곳에서 동시에 시작가능하기 때문이다. 따라서 기존에 어느 한곳에서 출발한다는 개념을 잊어야한다. 이 문제는 3개의 포인트가 있다.

1. 토마토가 다 익은 곳들을 한번에 찾아서 queue에 넣고 시작하는 것이 첫번째 포인트
2. 날짜를 세야하므로 현재 queue에 담겨있는 요소들만 선택해서 한 루틴을 돌려야한다는 것이 두번째 포인트
3. 마지막으로 토마토가 익지 못한 경우도 있을 것인데, 그걸 찾는 것이 마지막 포인트