[백준] 7576. 토마토 풀이 / Python, JavaScript

7576번: 토마토

7576. 토마토

접근한 방법

인접한 토마토부터 확인해야하니 BFS로 접근해야 하지만 익은 토마토가 여러개 분포하는 경우가 문제입니다. 

큐를 2개 사용하여 해결했습니다. 우선 주어진 배열에서 익은 토마토를 모두 체크하여 큐1에 넣고 큐2는 빈 큐로 만들어줍니다.

 

BFS로 진입하여 현재 큐1에 들어있는 익은 토마토의 상하좌우를 모두 체크해 큐2에 넣어줍니다. 큐1에 넣지 않는 이유는 무한 루프를 돌지 않기 위해서입니다.

다음번 루프에서는 현재 큐가 큐2가 될 것이고 큐2에 들어있는 익은 토마토의 상하좌우를 체크해 큐1에 넣어줍니다.

이런식으로 큐1과 큐2를 연달아 사용하는 과정에서 카운트를 체크해주면 정답을 구할 수 있습니다.

 

Python

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
arr = [list(map(int, list(input().split()))) for _ in range(n)]
dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
from collections import deque
q1, q2 = deque(), deque()

def bfs(cnt):
    while q1 or q2:
        cnt += 1
        currq = q1 if q1 else q2
        othrq = q1 if q2 else q2
        while currq:
            qr, qc = currq.popleft()
            for i in range(4):
                nr, nc = qr + dr[i], qc + dc[i]
                if nr < 0 or nc < 0 or nr >= n or nc >= m:
                    continue
                if not arr[nr][nc]:
                    arr[nr][nc] = 1
                    othrq.append((nr, nc))
    return cnt
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q1.append((i, j))
result = bfs(-1)
for i in range(n):
    for j in range(m):
        if not arr[i][j]:
            result = -1
            break
print(result)

JavaScript