(Python/🥇5)백준 알고리즘 7576번: 토마토

728x90

문제 출처: https://www.acmicpc.net/problem/7576

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

풀이:

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

M, N = map(int,input().split(" "))


map = [list(map(int, input().split())) for i in range(N)] # 문제 그대로 가져옴
move = [(0,1),(0,-1),(1,0),(-1,0)] # 이동방향 상하좌우
Q = deque([])
for i in range(N):
    for j in range(M):
        if map[i][j] == 1:
            Q.append([i, j])

while Q:
    x,y = Q.popleft()
    for a, b in move:
        nx, ny = x+a, y+b
        if 0 <= nx < N and 0 <= ny < M and map[nx][ny] == 0:
            Q.append((nx,ny))
            map[nx][ny] = map[x][y] + 1

res = 0
for i in map:
    if 0 in i:
        print(-1)
        exit()
    res = max(res,max(i))
print(res-1)

bfs 를 사용해서 풀면 된다.

대신 처음에 Q에 담을때 토마토가 담아있는 곳을 다 담아주어야한다.

다 채운후에 map 에 0이 있으면 다 익은게 아니므로 -1을 출력하고 프로그램을 종료해야한다.

처음에 1부터 시작하므로 res -1 을 해줘야함