[백준][Python] 7576 토마토

그래프, bfs / 골드 5

 

🍅

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

7576번: 토마토

 

 

내 풀이

from collections import deque

def bfs():
    q = deque()
    for i in range(len(tomato_index)):
        q.append((tomato_index[i][0], tomato_index[i][1]))

    while q:
        cx, cy = q.popleft()

        for k in range(4):
            nx, ny = cx + dx[k], cy + dy[k]
            if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[cx][cy] + 1
                q.append((nx, ny))


M, N = map(int, input().split()) # 가로, 세로
tomato = [[]* M for _ in range(N)]
ans = 0
not_well_done = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
tomato_index = []

for i in range(N):
    tomato[i] = list(map(int, input().split()))

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            tomato_index.append([i,j])

bfs()

for i in range(N):
    ans = max(ans, max(tomato[i])-1)
    not_well_done += tomato[i].count(0)
    if not_well_done > 0:
        ans = -1
        break

print(ans)

bfs(너비 우선 탐색)으로 풀었다.

 

 

코드 설명

 

배열 전체를 돌면서, 1(익은 토마토)을 만난 경우 해당 토마토의 좌표를 tomato_index에 추가한다.

bfs를 호출한다.

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            tomato_index.append([i,j])

bfs()

 

연산이 끝난 뒤 새롭게 바뀐 배열을 한 줄씩 검사하면서 모든 토마토가 익을 때까지의 최소 날짜를 도출한다.

이때, 0(익지 않은 토마토)가 발견된다면, 토마토가 모두 익지 않은 상황이므로 정답은 -1이 된다.

for i in range(N):
    ans = max(ans, max(tomato[i])-1)
    not_well_done += tomato[i].count(0)
    if not_well_done > 0:
        ans = -1
        break

 

 

✔️ bfs 함수

 

tomato_index에 저장되어있는 익은 토마토들의 좌표를 모두 deque에 추가한다.

q = deque()
    for i in range(len(tomato_index)):
        q.append((tomato_index[i][0], tomato_index[i][1]))

 

현재 좌표를 기준으로 상하좌우를 검사한다.

새로운 좌표가 범위 안에 있으며, 아직 방문하지 않은 익지 않은 토마토(0)인 경우,

기존 좌표 값에 1을 더해주고(토마토가 익을 때까지 걸리는 날짜를 의미함), deque에 새 좌표를 추가한다.

while q:
    cx, cy = q.popleft()

    for k in range(4):
        nx, ny = cx + dx[k], cy + dy[k]
        if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
            tomato[nx][ny] = tomato[cx][cy] + 1
            q.append((nx, ny))

 

 

어려웠던 점

 

계속해서 시간초과가 발생했다.

처음에 for문 안에서 bfs를 여러번 호출하는 방식으로 코드를 짜서 시간이 오래 걸렸던 것 같다.

 

1(익은 토마토)의 좌표를 모두 찾아 tomato_index 리스트에 저장한 뒤, bfs를 한 번만 호출하는 것이 핵심이었다.

 

집착의 흔적 ,,