원본은 여기!
접근
주석으로 자세히 설명해 두었으니 혹시 감을 못잡겠다 싶어서 찾아온 거라면 실눈뜨고 주석만 쭉 읽어보면 좋을 것 같다!
아이디어는 다음과 같다. 물론 매번 모든 칸을 확인하면서 익은 토마토에 인접한 안익은 토마토를 익게 처리해줄 수도 있지만, 이미 익은 토마토에 둘러싸인 익은 토마토에 대해서 그 주변에 안익은 토마토가 있는지 다시 확인하는건 매우 비효율적일 것이다.
대신 스물스물 침식해나가듯이 안쪽 말고 바깥쪽의 익은 토마토에 대해서만 주변에 익힐 토마토가 있는지 확인해준다면, 위와 같은 낭비가 없겠지? 뭐랄까 곰팡이가 퍼져 나가듯이,, 경계 부분이 너비 우선(Breadth-First)으로 익은 토마토의 영역이 확장되는 그림을 생각해보면 될 것 같다.
그렇게 반복하다가 격자에 변화가 없음을 감지하면(더이상 익은 토마토가 없으면) 루프를 종료하면 된다. 코드에서는 ripped라는 이름의 플래그를 써서, 하루가 시작하기 전에 초기화해주고(ripped = False) 아직 처리되지 않았으나 익은 토마토와 붙어 있는 경우 어떤 토마토가 익었음을 표시해주었다(ripped = True).
그렇게 하루가 끝났을 때 만약 익은 토마토가 없다면 격자에 더이상 변화가 있을 수 없음을 의미하므로 바깥 while문을 탈출하면 된다.
마지막으로 최종 결산을 할 때(루프 바깥)는 순회하면서 안 익은 상태에서 익은 상태로 바뀐 토마토의 갯수가 순회를 시작하기 전에 기록해놓은 안 익은 토마토의 갯수와 같으면 모든 토마토가 익은 상태로 변한 것이고, 그렇지 않으면 익을 수 없는 토마토가 존재하는 것이므로 -1을 반환하면 된다.
코드,, 전에 잠깐!
사실 다 풀어놓고 맨 마지막에 -1을 반환할지 말지 판단하는 조건을 틀려서 엣지 케이스를 찾아봤었다. 이 글을 보고 있다면 아마 나처럼 공부하는 사람일 것 같은데, 가능하면 코드를 보기 전에 이 케이스 먼저 검토해보길 바란다.
입력:
5 3
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
출력:
-1(질문 남겨주신 tnals1178님과 답변 남겨주신 jaydenryu11님께 감사합니다!)
코드
from typing import List
from sys import stdin
from collections import deque
input = stdin.readline
# 익은 토마토
RIPPED = 1
# 안 익은 토마토
NOT_RIPPED = 0
# 빈 칸
EMPTY = -1
# 상하좌우
VECTOR = ((-1, 0), (1, 0), (0, -1), (0, 1))
def solution(storage: List[List[int]]):
n, m = len(storage), len(storage[0])
# 격자를 벗어나는지 확인하는 함수
def in_range(i: int, j: int) -> bool:
return i in range(n) and j in range(m)
# 방문 여부를 체크하기 위한 배열로, RIPPED만 저장되어야 한다.
visited = [[False] * m for _ in range(n)]
# BFS로 익은 토마토를 하나씩 꺼내서 방문 처리해주고,
# 상하좌우로 인접한 안익은 토마토들을 익은 상태로 바꾼 다음 enqueue하여
# 다음 `while True:` iteration에서 방문 처리되도록 함
queue = deque()
# 격자 전체에서 안익은 토마토의 갯수를 구함
not_ripped_tomato_cnt = 0
for i in range(n):
for j in range(m):
if storage[i][j] == RIPPED:
queue.append((i, j))
elif storage[i][j] == NOT_RIPPED:
not_ripped_tomato_cnt += 1
# 안 익은 상태에서 익은 상태로 바뀐 토마토의 갯수를 저장
# 격자를 순회하며 모든 토마토가 익게 될 경우 changed_tomato_cnt와 not_ripped_tomato_cnt가 같아야 함
changed_tomato_cnt = 0
# 경과된 일수를 저장함
days = 0
# 더이상 익는 토마토가 발생하지 않으면 루프를 종료함
while True:
# Iteration 안에서 계속해서 익은 토마토와 인접한 안익은 토마토가 enqueue 되는데,
# 그럼 날짜가 얼만큼 지났는지 알 수 없으므로 반복을 시작하는 시점에 큐에 들어있던
# 익은 토마토에 대해서만 dequeue를 해주어야 함
current_queue_length = len(queue)
# 이번 큐 iteration에서 안 익은 토마토가 익은 상태로 바뀌는지 확인하기 위한 플래그
ripped = False
for _ in range(current_queue_length):
i, j = queue.popleft()
assert storage[i][j] == RIPPED, f"{(i, j)} is not ripped tomato"
# 방문 처리되지 않은 토마토인 경우
if not visited[i][j]:
# 방문 처리 해주고
visited[i][j] = True
# 해당 토마토를 기준으로 상하좌우 방향에 있는 격자에 대해
for dy, dx in VECTOR:
next_i, next_j = i + dy, j + dx
# 해당 격자에 안 익은 토마토가 들어가 있는 경우
if (
in_range(next_i, next_j)
and storage[next_i][next_j] == NOT_RIPPED
):
# 해당 격자를 익은 것으로 처리하고
storage[next_i][next_j] = RIPPED
changed_tomato_cnt += 1
ripped = True
# 다음 queue iteration에서 방문 처리 될 수 있도록 enqueue함
queue.append((next_i, next_j))
# 더이상 익는 토마토가 발생하지 않으면 루프를 종료함
if not ripped:
break
# 오늘 익은 토마토가 존재한다면, 내일 새로운 토마토가 또 익을 수 있으므로 하루를 넘김
else:
days += 1
# 안 익은 상태에서 익은 상태로 변한 토마토의 개수가 순회 전의 안 익은 토마토 개수와 같으면 모든 토마토가 익은 것
# 그렇지 않다면 안 익은 토마토가 있는 것이므로 -1 반환
return days if changed_tomato_cnt == not_ripped_tomato_cnt else -1
if __name__ == "__main__":
n, m = map(int, input().split())
storage = [list(map(int, input().split())) for _ in range(m)]
print(solution(storage))