[알고리즘/백준] 7576번 토마토

(BFS) 7576번 토마토 

 

7576번: 토마토

 

 

 

---

접근 방법

토마토가 보관 당시 익어있다면 배열에 1이라고 저장되어 있다. 이러한 토마토를 미리 시작 전 queue에 담아 BFS를 한다.

 

for i in range(N):
    storage.append(list(map(int, input().split())))
    ripe_tomatoes.extend([(i, j) for j in range(M) if storage[-1][j] == 1])

 

BFS를 할 때 위, 아래, 좌, 우 좌표로 움직인다음 그 안에 토마토가 들어있으면서 아직 익지 않은 토마토 라면 배열의 값을 +1 하여 저장하여준다. 이 값은 익는 일수를 의미한다. 

맨 처음 저장할 때 1인 토마토가 사실은 0일 때 익어있다는 것을 의미하고, 다른 토마토들은 (배열 값 - 1)일에 익은 것이다.

따라서 출력할 때에는 배열의 가장 큰 값을 찾은 후 -1한 값(cnt)을 출력한다.

 

while queue:
        node = queue.popleft()
        for a, b in cor_list:
            x, y = node[0] + a, node[1] + b
            if 0 <= x < N and 0 <= y < M:
                if storage[x][y] == 0:
                    queue.append((x, y))
                    storage[x][y] = storage[node[0]][node[1]] + 1
                    cnt = storage[node[0]][node[1]]

 

이때 모든 토마토가 익지 않았다면 배열에 0인 값이 하나 이상 포함되어 있기 때문에 -1을 출력한다.

 

 for i in range(N):
        for j in range(M):
            if storage[i][j] == 0:
                return (-1)

---

 

코드

 

처음 제출 시 python3 시간 초과 

 

: 2차원 리스트를 1차원 리스트로 만든 후 max 값을 구하기 위해 아래의 코드처럼 사용  ▶ 이 부분이 시간 초과

 

max(sum(storage, []))

 

import sys
from collections import deque

input = sys.stdin.readline

def BFS(storage, ripe_tomatoes, N, M):
    queue = deque(ripe_tomatoes)
    cor_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        node = queue.popleft()
        for a, b in cor_list:
            x, y = node[0] + a, node[1] + b
            if 0 <= x < N and 0 <= y < M:
                if storage[x][y] == 0:
                    queue.append((x, y))
                    storage[x][y] = storage[node[0]][node[1]] + 1
    if sum(storage, []).count(0) != 0:
        return (-1)
    return (max(sum(storage, [])) - 1)


M, N = map(int, input().split())
storage = []
ripe_tomatoes = []

for i in range(N):
    storage.append(list(map(int, input().split())))
    ripe_tomatoes.extend([(i, j) for j in range(M) if storage[-1][j] == 1])

print(BFS(storage, ripe_tomatoes, N, M))

---

최종 제출 코드

 

앞에서 시간 초과 났던 부분을 이중 반복문으로 수정 / BFS 할 때 같이 max값을 구해줌

 

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

def BFS(storage, ripe_tomatoes, N, M):
    queue = deque(ripe_tomatoes)
    cor_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 0
    while queue:
        node = queue.popleft()
        for a, b in cor_list:
            x, y = node[0] + a, node[1] + b
            if 0 <= x < N and 0 <= y < M:
                if storage[x][y] == 0:
                    queue.append((x, y))
                    storage[x][y] = storage[node[0]][node[1]] + 1
                    cnt = storage[node[0]][node[1]]

    for i in range(N):
        for j in range(M):
            if storage[i][j] == 0:
                return (-1)
    return (cnt)


M, N = map(int, input().split())
storage = []
ripe_tomatoes = []

for i in range(N):
    storage.append(list(map(int, input().split())))
    ripe_tomatoes.extend([(i, j) for j in range(M) if storage[-1][j] == 1])

print(BFS(storage, ripe_tomatoes, N, M))

 

 

---

참고했던 사이트

 

 

파이썬을 파이썬답게 - 2차원 리스트를 1차원 리스트로 만들기 - from_iterable