문제설명
토마토를 보관하는 창고에 토마토들이 담긴 상자가 있습니다. 토마토 상자에는 잘익은 토마토가 들어있는 칸, 아직 익지않은 토마토가 들어있는 칸, 토마토가 들어있지 않은 칸이 있습니다. 잘 익은 토마토들은 하루마다 상하좌우로 인접해있는 아직 익지않은 토마토들을 잘 익은 토마토들로 만들어 줄 때 상자안의 토마토들이 모두 익기 위해서는 며칠이 걸리는지 출력하는 문제입니다.
작동 순서
1. 상자의 크기를 입력받습니다.
2. 상자안 토마토의 상태를 입력받습니다.(0은 익지 않은 상태, 1은 잘 익은 상태, -1은 토마토가 없는 상태)
3. 상자안의 익지않은 토마토의 개수를 확인하고 잘 익은 토마토의 위치를 큐에 집어넣습니다.
4. 잘 익은 토마토의 위치로부터 상하좌우를 확인하고 빈칸인 경우 넘어가고 잘 익은 토마토인 경우 그 토마토의 위치를 임시큐에 삽입, 익지않은 토마토인 경우 그 토마토를 익은 토마토로 만들고 위치를 임시큐에 삽입합니다.
5. 해당 날짜의 토마토 탐색이 끝나면 임시큐에 있는 토마토들의 위치를 큐에 삽입하고 날짜를 +1해줍니다.
6. 모든 연산이 끝난 뒤에 소요된 날짜를 출력해줍니다.(day-1을 출력하는 이유는 모든 토마토가 익은 날에도 다음날에 넘어갈 때 하루를 더해주기 때문입니다.)
소스코드
import sys
from collections import deque
M, N = map(int, sys.stdin.readline().split(" "))
box = [[0 for _ in range(M)] for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
unripe = 0
day = 0
queueX = deque()
queueY = deque()
TempX = deque()
TempY = deque()
for i in range(N):
box[i][:] = map(int, sys.stdin.readline().split())
for j in range(M):
if box[i][j] == 0:
unripe += 1
if box[i][j] == 1:
queueX.append(i)
queueY.append(j)
if unripe > 0:
while len(queueX) > 0:
X = queueX.pop()
Y = queueY.pop()
for i in range(4):
if N > X + move[i][0] >= 0 and M > Y + move[i][1] >= 0:
if not visited[X + move[i][0]][Y + move[i][1]]:
visited[X + move[i][0]][Y + move[i][1]] = True
if box[X + move[i][0]][Y + move[i][1]] == 1:
TempX.append(X + move[i][0])
TempY.append(Y + move[i][1])
elif box[X + move[i][0]][Y + move[i][1]] == 0:
TempX.append(X + move[i][0])
TempY.append(Y + move[i][1])
unripe -= 1
if len(queueX) == 0:
while len(TempX) > 0:
queueX.append(TempX.pop())
queueY.append(TempY.pop())
day += 1
if unripe > 0:
print(-1)
else:
print(day - 1)
else:
print(0)후기
파이썬으로 정답을 제출하니 자꾸 시간초과가 나와서 pypy로 제출했더니 바로 통과가 된 코드입니다. 파이썬으로도 통과할 수 있도록 코드 수행 시간을 단축시킬 수 있는 방법을 공부해야 할 것 같습니다. 그리고 pypy에서도 queue로 구현했을 때는 시간 초과가 나오는데 deque로 구현하면 정답처리가 되네요. 눈에 보이는 시간복잡도만 신경쓸게 아니라 해당 코드 자체의 성능도 신경쓰면서 코딩을 해야 할 것 같습니다.
