백준 7576: 토마토 (Python)

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

미로 찾기랑 비슷한 문제다

처음엔 BFS를 동시에 돌려야 하나.....? 하고 혼자 엄청 고민했는데

그냥 큐에 있는 걸 전부 돌리기만 해도 된다는 걸 깨달음

 

맨 마지막 좌표에서 끝나는 것이 아니기 때문에 결과값은 최대값!

처음 시작을 1로 하기 때문에 결과값은 -1 해주기!

 

from collections import deque

m, n = map(int, input().split())
tomato = []

for i in range(n):
    tomato.append(list(map(int, input().split())))

queue = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append([i, j])

def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            mx = x + dx[i]
            my = y + dy[i]

            if mx < 0 or mx >= n or my < 0 or my >= m:
                continue

            if tomato[mx][my] == 0:
                queue.append([mx, my])
                tomato[mx][my] = tomato[x][y] + 1

bfs()
for i in range(n):
    if 0 in tomato[i]:
        res = -1
        break
    else:
        res = max(map(max, tomato)) - 1

print(res)

 

pypy3로 채점했음에도 불구하고 엄청난 시간이 걸렸다,,,

 

from collections import deque

m, n = map(int, input().split())
tomato = []

for i in range(n):
    tomato.append(list(map(int, input().split())))

queue = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append([i, j])

def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            mx = x + dx[i]
            my = y + dy[i]

            if mx < 0 or mx >= n or my < 0 or my >= m:
                continue

            if tomato[mx][my] == 0:
                queue.append([mx, my])
                tomato[mx][my] = tomato[x][y] + 1

bfs()
res = max(map(max, tomato)) - 1
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            res = -1
            break

print(res)

 

res 값 정하는 부분만 바꿨는데도 시간이 확 단축됐다

처음 풀었던 코드는 내가 짜면서도 비효율적이라고 생각하긴 했다,,, ㅎㅏ하