•
문제 설명
BFS를 통해 공간(토마토 창고)을 탐색하고, 불필요한 코드를 줄여 시간 초과를 막아야한다.
•
실패 코드
본인은 BFS를 통한 동작은 성공했지만, 시간 초과에서 고전했다.
pypy3로 변경하면 시간 초과가 뜨지 않는다고 해서 시도했지만, 동일하게 시간 초과가 뜨기도 했고 실제로 테스트에서는 pypy3로 변경해서 제출할 수 도 있는 거도 아니기 때문에 python3로 해결해야 된다고 생각했다.
동작은 되지만 시간 초과가 발생하는 코드
•
성공 코드
성공 코드 전체 확인
실패한 코드에서 여러 부분을 개선하였다.
1.
고립된 토마토 구하기 → bfs 동작이 끝난 후, 익지 않은 토마토가 있다면 그 토마토는 고립된 토마토이며 -1 을 반환한다.
이 부분을 보고, 골드 레벨부터는 단순히 동작보다 특정 조건에 만족하는 방법이 여러개이며 가장 효율적인 방법을 찾는 법이 중요한것을 크게 깨달았다.
본인은 고립된 토마토를 일일히 값을 체크하며 구했지만, 그냥 결과를 보고 확인만 해도 알 수 있었기 때문이다.
2.
1일 변화량이 누적된 큐를 조회하는 방법 → 아래와 같은 방법으로 탐색 방법을 변경하였다.
a.
for문을 사용하여 큐의 모든 좌표를 한번씩 사용한다.
b.
각 좌표의 토마토와 연결되어 새롭게 익은 토마토의 좌표는 큐에 저장된다.
c.
1번의 과정으로 기존의 토마토 좌표는 모두 큐에서 빠져나갔으며, 2번 과정으로 새로운 좌표가 누적된 상태이다.
d.
이 큐가 2번 과정에서 새롭게 저장된 좌표가 없다면, 익을 수 있는 토마토는 모두 익은것이기 때문에 탐색을 종료한다.
이건 문법적인 이해가 부족한건데, 기존의 실패한 코드는 아래와 같은 방법을 생각했다.
다시 작성해봐도 벌써부터 불필요한 변수 사용과 동작으로 불편함이 느껴진다. 
a.
큐에서 좌표를 하나 뽑는다.
b.
해당 좌표를 사용해 다른 리스트(실패 코드의 ONE_DAY 등)에 하루동안 새롭게 익은 토마토(1일 변화량)의 좌표를 누적한다.
c.
a-b를 큐가 빌때까지 반복한다.
d.
b 과정으로 누적된 1일 변화량 리스트 값을 빈 큐에 추가(queue.extend())해준다.
e.
고립되지 않은 모든 토마토의 갯수와 익은 토마토의 갯수가 일치할때까지 반복한다.
•
코드 설명
처음부터 이미 익은 상태의 토마토 좌표를 구한다. 이 좌표는 큐의 삽입된 상태로 시작한다.
...
# 연결되지 않은 토마토 존재 여부와 이미 익은 토마토 확인
for i in range(N):
for j in range(M):
# 이미 익은 상태인 토마토 기록
if TOMATO[i][j] == 1:
START.append((i, j))
print(bfs(TOMATO, START, M, N))
Python
복사
3가지 조건에 만족하는 토마토는 큐에 추가되며, 익은 상태(1)로 변경된다.
1.
토마토 창고의 범위를 벗어난 좌표가 아니다.
2.
토마토가 들어있지 않은 칸(-1)의 좌표가 아니다.
3.
토마토가 익지 않은 상태(0)이어야 한다.
...
# for문으로 반복하여, 이전에 큐에 쌓인 모든 값(1일 변화량)을 모두 처리한다.
for _ in range(len(queue)):
y, x = queue.popleft()
for i in range(4):
if x+X[i] < 0 or x+X[i] >= M or y+Y[i] < 0 or y+Y[i] >= N:
continue
elif TOMATO[y+Y[i]][x+X[i]] == -1:
continue
elif TOMATO[y+Y[i]][x+X[i]] == 0:
TOMATO[y+Y[i]][x+X[i]] = 1
queue.append((y+Y[i], x+X[i]))
...
Python
복사
새롭게 익은 토마토 좌표를 제외한 기존의 토마토 좌표를 모두 사용했다면, 날짜 하루를 추가한다.
참고로 날짜는 0일부터 시작이다. 즉 모든 토마토가 이미 익은 상태이거나, 추가로 익을 토마토가 없다면 0이 정답이다.
무조건 한번은 while()문을 끝내며, days값에 1은 무조건 1번은 추가되기 때문에 -1로 초기값을 설정한 것이다.
from collections import deque
def bfs(TOMATO, START, M, N):
X = [-1, 1, 0, 0]
Y = [0, 0, -1, 1]
queue = deque(START)
days = -1
# 더 이상 추가 변화가 없을 때
while queue:
# for문으로 반복하여, 이전에 큐에 쌓인 모든 값(1일 변화량)을 모두 처리한다.
for _ in range(len(queue)):
...
days += 1
...
return days
...
Python
복사
만약 모든 토마토를 탐색하였지만, 안익은 토마토가 존재한다면 그 토마토는 고립된 토마토이며 문제에서는 고립된 토마토가 존재하면 무조건 -1을 반환하라고 한다. 그래서 -1를 반환한다.
def bfs(TOMATO, START, M, N):
...
# 모든 작업이 끝났지만, 아직도 익지 않은 토마토 -> 고립된 토마토 존재
for i in TOMATO:
for j in i:
if j == 0:
return -1
return days
...
Python
복사