[Python] 7576 - 토마토 (골드4)

1. 문제 설명

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

7576번: 토마토

 

---

2. 아이디어

치즈 문제(BOJ - 2636)와 굉장히 유사한 문제지만 이번에는 처음에 주어진 그래프를 통해서

익은 토마토의 위치를 시작지점으로 큐에 담아야 한다.

또한 그 과정에서 토마토가 들어있지 않은 구간은 방문한 구간으로 처리하여 bfs로 접근을 방지한다.

 

이러면 사실상 준비는 끝났고 그냥 bfs 돌려버리면 된다.

다만 여기서 토마토 정보는 따로 건들지 않았다. 그냥 visited 리스트의 방문여부로 모두 해결했다.

bfs 시작 전에 처음부터 익어있던 토마토와 토마토가 들어있지 않은 자리는 모두 걸러냈으므로

이후에는 익지 않은 토마토지만 방문처리가 되어있다면 이미 익은 토마토라고 간주할 수 있다.

 

day 체크는 어떻게 할 수 있는가?

큐는 선입선출(FIFO) 자료구조임을 이용하면 된다.

처음에 익은 토마토를 모두 큐에 담고 길이를 체크한다.

큐에서 data를 하나씩 꺼낼 때마다 count를 1씩 차감하다보면 0이 되고 아직 큐가 비어있지 않은 상태가 오면

가장 처음에 들어있던 익은 토마토를 기준으로 bfs를 한 바퀴 모두 돌렸다는 이야기가 된다.

그렇다면 현재 큐에 담겨있는 data는 day 2의 익은 토마토 정보가 되므로 다시 길이를 체크한다.

 

이러다보면 언젠가 반복이 끝날 것이고,

마지막으로 visited를 훑어보면서 방문 처리가 되지 않은 곳이 남아있다면 -1을 리턴하고

그렇지 않으면 누적된 결과값을 리턴하면 끝난다.

 

---

3. 코드

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

def bfs(box, n, m):
    queue = deque()
    vector = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[0]*m for _ in range(n)]
    for row in range(n):
        for col in range(m):
            if box[row][col] == 1:
                visited[row][col] = 1
                queue.append([row, col])
            if box[row][col] == -1:
                visited[row][col] = 1
    cnt = len(queue)
    ans = 0
                
    while queue:
        y, x = queue.popleft()        
        cnt -= 1
        for q, p in vector:
            m_y = y + q
            m_x = x + p
            if 0 <= m_y < n and 0 <= m_x < m:
                if not visited[m_y][m_x] and box[m_y][m_x] == 0:
                    queue.append([m_y, m_x])
                    visited[m_y][m_x] = 1
                elif not visited[m_y][m_x]:
                    visited[m_y][m_x] = 1
        if cnt == 0 and queue:
            ans += 1
            cnt = len(queue)
    for i in visited:
        for j in i:
            if j == 0:
                return -1
    return ans

def solution():
    m, n = map(int, input().split())
    box = [list(map(int, input().split())) for _ in range(n)]
    
    print(bfs(box, n, m))


solution()