[백준 알고리즘] 7576번: 토마토 (Python / 파이썬)

문제 접근

헷갈렸던 문제이다.

bfs를 사용하는데 시작 지점이 여러개다.

단순히 queue 사이클이 몇번 돌아갔는지 체크하면 당연히 더 큰 값이 나와 틀릴 것이기 때문에

한 사이클에 몇개의 요소가 큐에 들어갔고, 그것들에 의해서는 몇개가 큐에 추가되었는지 체크해야 한다.

temp, count, answer 세 개의 변수를 사용해서 특정 주기에 초기화시켜서 풀었다.

 

예를 들어,  시작점(1)이 2개, 그 시작점으로 인해 생긴 것(2)이 2개, (2)에 의해 3개가 큐에 들어갔다면

날짜 카운트를 bfs 반복 주기의 2번째, 4번째(2+2), 7번째(4+3)마다 해줘야 한다.

내가 짠 대로 하면 마지막 토마토까지 다 익고 나서 그 토마토가 영향을 주는 시간까지 고려되기 때문에 -1을 해준다.

 

불가 판단(-1 출력)은 입력될 때 벽 개수를 미리 세서,

모든 탐색 및 변환이 끝난 후에 전체 익은 토마토 수  !=  전체 노드 - 벽 개수 를 확인한다. 다르다면 익지 않은 것이 있다는 것이므로 -1을 출력하면 된다.

 

정답 코드

# 7576번: 토마토

import sys
from collections import deque

def bfs(map, riped_tomatoes):
    queue = deque()
    count = 0
    temp = 0
    answer = 0
    total_change = 0
    for riped_tomato in riped_tomatoes: # 시작점 여러개 큐에 넣기
        queue.append(riped_tomato)
        temp += 1
        total_change += 1
    dx, dy = [0, -1, 1, 0], [1, 0, 0, -1]

    j = 1
    while queue:
        cur = queue.popleft()
        for i in range(4):
            nx, ny = cur[0] + dx[i], cur[1] + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if map[nx][ny] == 0:
                    queue.append((nx, ny))
                    map[nx][ny] = 1
                    count += 1
                    total_change += 1
        if j == temp:
            answer += 1
            temp = count
            count = 0
            j = 0
        j += 1
    return answer - 1, total_change

# 입력 부분
m, n = map(int, sys.stdin.readline().split())
map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
start_list = []
wall_count = 0

# 시작점(이미 익어 있는 토마토들) 탐색
for i in range(n):
    for j in range(m):
        if map[i][j] == 1:
            start_list.append((i, j))

# 벽(-1) 수 탐색
for i in range(n):
    for j in range(m):
        if map[i][j] == -1:
            wall_count += 1

answer, total = bfs(map, start_list)

if total != n * m - wall_count: #불가 여부 판단
    print(-1)
else: print(answer)

 

---

7576번: 토마토