백준 7576 토마토 (BFS, 행렬 그래프, python)

이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보게 되었다.

 

원리는 어렵지 않다.

1. 토마토가 존재하는 곳을 찾아서 큐에 넣어준다.

2. 큐에서 하나씩 꺼내며 너비탐색을 진행한다.

3. 탐색이 끝나면 익지 않은 토마토가 존재하는지 확인한다.

4. 전부 익었다면 걸린 날짜를 출력, 익지 않은게 있다면 -1을 출력한다.

 

이를 토대로 코딩을 진행했다. 그러나 아래의 코드는 시간초과로 쓸수가 없었다.

from collections import deque
m,n = map(int, input().split())
L = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    L.append([-1]+tmp+[-1])
# 패딩 설정
L = [[-1 for i in range(m+2)]] + L + [[-1 for i in range(m+2)]]
# 초기 익은 토마토 위치 큐에 넣기
q = deque([])
for i in range(1,n+1):
    for j in range(1,m+1):
        if L[i][j] == 1:
            q.append((i,j,0))
# 토마토 익히기 시작!
num = 0
visited = []
while q:
    t = q.popleft()
    if t not in visited:
        visited.append(t)
        i,j,z = t    
        num = z
        L[i][j] = 1
        # 동서남북 확인하자~
        tmp = []
        if L[i][j+1] == 0:#동
            tmp.append((i,j+1,z+1))
        if L[i][j-1] == 0:#서
            tmp.append((i,j-1,z+1))
        if L[i+1][j] == 0:#남
            tmp.append((i+1,j,z+1))
        if L[i-1][j] == 0:#북
            tmp.append((i-1,j,z+1))
        q += tmp
# 0이 남았는지 확인
check = True
for i in range(n):
    for j in range(m):
        if L[i][j] == 0:
            check = False
if check == True:
    print(num)
else:
    print(-1)

 

그래서 다른 고수의 코드를 보니 for를 더 적게 쓰기위해 입력과 동시에 익은 토마토를 탐색한다.

또한 좌우상하의 오프셋을 배열에 넣어 좌우상하를 빠르게 탐색하도록 만들었다.

아래는 고수의 코드이다.

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

def bfs(m,n, box):
    #좌우상하
    dx = [0,0,1,-1]
    dy = [-1,1,0,0]
    days = -1
    while q:
        days += 1
        for _ in range(len(q)):
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if (0 <= nx < n) and (0 <= ny < m) and (box[nx][ny] == 0):
                    box[nx][ny] = box[x][y] + 1
                    q.append([nx,ny])
    for b in box:
        if 0 in b:
            return -1
    return days
m,n = map(int, r().split())
box, q = [], deque([])
for i in range(n):
    row = list(map(int,r().split()))
    for j in range(m):
        if row[j] == 1:
            q.append([i,j])
    box.append(row)
print(bfs(m,n,box))

 

살짝 복잡해 보이지만 로직의 연산을 더 최소화 하여 탐색을 하게 된다. 

내 수준에서는 따라해보는게 다였지만 다음에 이러한 방식으로 풀어야겠다.