/* 문제 */ 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
처음부터 결과는 제대로 나왔지만 채점할 때 계속해서 오류가 나거나 시간 초과가 돼서 오래 걸린 문제다.
깊이 들어가는 것이 아니라 인접한 토마토부터 익으므로 bfs를 이용하는 문제고 토마토가 익는데 하루가 걸리므로 최단 거리 문제와 동일하게 풀 수 있다.
익은 토마토가 여러 곳에 있기 때문에 처음에는 큐를 여러 개 사용하려고 했다. 각각의 시작점에 대한 큐를 여러 개 만든 후 하나의 리스트에 담아 접근하는 식이다.
# IndexError 오류 코드
from collections import deque
import sys
input = sys.stdin.readline
def bfs(graph, starts):
global n, m
queues = []
for s in starts:
queues.append(deque([s]))
while len(queues) != 0:
for i in range(len(queues)):
v = queues[i].popleft()
x, y = v[0], v[1]
if x > 0 and graph[x-1][y] == 0:
queues[i].append([x-1, y])
graph[x-1][y] = graph[x][y] + 1
if x < n-1 and graph[x+1][y] == 0:
queues[i].append([x+1, y])
graph[x+1][y] = graph[x][y] + 1
if y > 0 and graph[x][y-1] == 0:
queues[i].append([x, y-1])
graph[x][y-1] = graph[x][y] + 1
if y < m-1 and graph[x][y+1] == 0:
queues[i].append([x, y+1])
graph[x][y+1] = graph[x][y] + 1
if len(queues[i]) == 0:
del queues[i]
m, n = map(int, input().split())
box = []
for _ in range(n):
box.append(list(map(int, input().split())))
zero = 0
starts = []
for i in range(n):
for j in range(m):
if box[i][j] == 1:
starts.append([i, j])
elif box[i][j] == 0:
zero += 1
if zero == 0:
print(0)
elif len(starts) == 0:
print(-1)
else:
bfs(box, starts)
if 0 in sum(box, []):
print(-1)
else:
print(max(sum(box, []))-1)
위와 같이 queues라는 리스트에 큐를 여러 개 담아 사용하려고 했는데, 다 사용한 큐를 삭제하는 과정에서 인덱스에러가 날 수밖에 없는 코드다. 인덱스에러를 피하기 위해 큐에 인덱스가 아니라 요소 방식으로 접근하고 remove()로 제거하면 정답이 나오지 않는다.
큐의 구조에 대해 조금만 생각했으면 이렇게 돌아가지 않았을 텐데...
또한 처음부터 모든 토마토가 익어있는 경우를 확인하기 위해 입력에 0이 있는지를 체크했는데, 이 경우 어차피 모든 칸이 1 또는 -1이기 때문에 최종 출력값은 0이 된다. 불필요하게 매번 비교 연산을 하며 시간을 잡아먹는 코드였다.
큐는 선입선출 방식이기 때문에 하나의 큐에 여러 시작점을 차례로 넣어주면 위의 코드에서 내가 하고자 했던 일을 똑같이 할 수 있다.
# 시간 초과 코드
from collections import deque
import sys
input = sys.stdin.readline
def bfs(graph, queue):
global n, m
while queue:
v = queue.popleft()
x, y = v[0], v[1]
if x > 0 and graph[x-1][y] == 0:
queue.append([x-1, y])
graph[x-1][y] = graph[x][y] + 1
if x < n-1 and graph[x+1][y] == 0:
queue.append([x+1, y])
graph[x+1][y] = graph[x][y] + 1
if y > 0 and graph[x][y-1] == 0:
queue.append([x, y-1])
graph[x][y-1] = graph[x][y] + 1
if y < m-1 and graph[x][y+1] == 0:
queue.append([x, y+1])
graph[x][y+1] = graph[x][y] + 1
m, n = map(int, input().split())
box = []
for _ in range(n):
box.append(list(map(int, input().split())))
queue = deque([])
for i in range(n):
for j in range(m):
if box[i][j] == 1:
queue.append([i, j])
if len(queue) == 0:
print(-1)
else:
bfs(box, queue)
res = sum(box, [])
if 0 in res:
print(-1)
else:
print(max(res)-1)
이번에는 불필요한 코드를 지우고 하나의 큐를 사용했다.
이 코드는 시간 초과가 떴는데, 그 이유가 혹시 sum을 사용해서인지 확인해봤다.
# 정답 코드
from collections import deque
import sys
input = sys.stdin.readline
def bfs(graph, queue):
global n, m
while queue:
v = queue.popleft()
x, y = v[0], v[1]
if x > 0 and graph[x-1][y] == 0:
queue.append([x-1, y])
graph[x-1][y] = graph[x][y] + 1
if x < n-1 and graph[x+1][y] == 0:
queue.append([x+1, y])
graph[x+1][y] = graph[x][y] + 1
if y > 0 and graph[x][y-1] == 0:
queue.append([x, y-1])
graph[x][y-1] = graph[x][y] + 1
if y < m-1 and graph[x][y+1] == 0:
queue.append([x, y+1])
graph[x][y+1] = graph[x][y] + 1
m, n = map(int, input().split())
box = []
for _ in range(n):
box.append(list(map(int, input().split())))
queue = deque([])
for i in range(n):
for j in range(m):
if box[i][j] == 1:
queue.append([i, j])
if len(queue) == 0:
print(-1)
else:
bfs(box, queue)
res = 0
for i in range(n):
for j in range(m):
if box[i][j] == 0:
print(-1)
exit()
if max(box[i]) > res:
res = max(box[i])
print(res-1)
문제는 sum이 맞았다. sum의 시간복잡도는 O(n)으로 비효율적이다.
2차원 리스트를 1차원 리스트로 만들기 위해 사용했던 sum을 지우고 다른 방법을 사용했더니 시간 초과가 되지 않았다. 이중 for문을 돌며 익지 않은 토마토가 나오면 바로 -1을 출력한 후 종료하고, 각 줄마다 최댓값을 구해 반복문을 정상적으로 빠져나갔을 경우 출력했다.
