[BOJ]7576 토마토 - python

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

큐를 이용한 BFS를 통해 풀수있는 문제입니다.

파이썬에서 collection 내장 모듈의 deque를 큐처럼 사용하여 BFS를 하였습니다.

코드를 보면 dy, dx를 이용하여 ny, nx를 구하는데, dy,dx는 방향을 나타내는 리스트로 각 인덱스 별로 짝을 이루어서 북,동,남,서 를 현재 좌표값에 더함으로써 현재위치에서 북, 동, 남, 서의 좌표값을 구하는것에 사용했습니다.

그리고 ny, nx는 인접한 배열의 좌표값이며, ny, nx가 익지 않은 토마토가 있는곳인지 체크하고 큐에 넣어주는 형식으로 BFS를 구현하였습니다.

import sys
import collections
 
input = lambda: sys.stdin.readline().rstrip()
 
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
 
 
def solve(n, m, box):
    qu = collections.deque()
    result = -1
 
    for i in range(n):
        for j in range(m):
            if box[i][j] == 1:
                qu.append((i, j))
 
    while qu:
        result += 1
        quLen = len(qu)
 
        for _ in range(quLen):
            cy,cx = qu.popleft()
 
            for i in range(4):
                ny = cy + dy[i]
                nx = cx + dx[i]
 
                if ny >= 0 and nx >= 0 and ny < n and nx < m and box[ny][nx] == 0:
                    box[ny][nx] = 1
                    qu.append((ny,nx))
 
    for i in range(n):
        for j in range(m):
            if box[i][j] == 0:
                return -1
 
    return result
 
 
m, n = map(int, input().split())
box = [[int(x) for x in input().split()] for _ in range(n)]
print(solve(n, m, box))