[BOJ] 7576번 토마토 / 사용언어 : 파이썬(python)

※ 문제링크 

7576번: 토마토

해당문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS를 구현하기 위해 파이썬에 내장되어 있는 collections의 deque를 사용했다. 기존의 문제들과 조금 차별점이 있다면 시작점이 1개가 아니라 여러개가 될 수 있다는 점이었기에 해당 부분에 초점을 두고 문제를 해결하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 2차원 리스트 형태로 변환한다.

2. 배열의 처음부터 마지막까지 2중 반복문을 이용하여 탐색하여 익은 토마토의 개수와 위치를 확인하여 queue에 넣어놓는다.

3. 리스트에 익은 토마토가 처음부터 없는 경우 -1을 출력하고, 익은 토마토가 있으면, BFS를 활용하여 queue가 빌 때까지 반복한다. (queue 비어있으면 더이상 익을 수 있는 경우가 없는 것으로 해석하면됨)

+ 수학에서의 x,y좌표와 배열상의 x,y좌표가 다른 점을 유념하고 코드를 작성하였다.

+ 입력받아야 하는 값들이 많다는 점을 고려하여 sys를 활용하였으며, 해당 함수 사용시에는 개행문자 사용에 유의하였다.

 

from collections import deque
import sys

def bfs(field, queue):
    K = len(queue)    
    for _ in range(K):
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if field[ny][nx] == 0:
                    field[ny][nx] = 1
                    queue.append([nx, ny])

M, N = map(int, input().split()) # M : x좌표 / N : y좌표
field = []
for _ in range(N):
    field.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = -1
queue = deque()

for x in range(M):
    for y in range(N):
        if field[y][x] == 1:
            queue.append([x, y])
check = len(queue)

if check == 0:
    sys.stdout.write(f'{-1}')
else:
    while True:
        if len(queue) == 0:
            break
        bfs(field, queue)
        cnt += 1
    raw = 0
    for i in range(N):
        if 0 in field[i]:
            raw += 1
    if raw > 0:
        sys.stdout.write(f'{-1}')
    else:        
        sys.stdout.write(f'{cnt}')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.