백준 - 토마토(Python) 복습

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

7576번: 토마토

1의 개수 : 익은 토마토

0의 개수 : 익지 않은 토마토

-1의 개수 : 토마토가 없는 곳

 

익은 토마토를 모두 큐에 넣고, 4방향으로 주변을 탐색(BFS)하면 된다.

주변 탐색 조건 :

1. 맵을 벗어나지 않는다.(row in range(m), col in range(n)

2. 익지 않은 토마토가 있다.(map[row][col] == 0)

 

최대한 탐색해서 만든 익힌 토마토의 개수가 전체 토마토의 개수와 같으면 성공 -> day 리턴

같지 않다(모두 익지 않았다.) -> -1 리턴

import sys
from collections import deque

directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def is_ripenable(row, col, map):
    if row not in range(0, len(map)) or col not in range(0, len(map[0])):
        return False
    elif map[row][col] == 0:
        return True
    return False

def solution(m, n, map):
    total_tomato_count = m * n
    ripen_tomato_count = 0

    non_ripen_tomatoes = deque()
    for row in range(n):
        for col in range(m):
            if map[row][col] == 1:
                ripen_tomato_count += 1
                non_ripen_tomatoes.appendleft((row, col))
            elif map[row][col] == -1:
                total_tomato_count -= 1

    if total_tomato_count == ripen_tomato_count:
        return 0

    day = 0
    while len(non_ripen_tomatoes) != 0 and ripen_tomato_count != total_tomato_count:
        current_size = len(non_ripen_tomatoes)
        for x in range(current_size):
            current_tomato_position = non_ripen_tomatoes.pop()
            for direction in directions:
                next_position = (current_tomato_position[0] + direction[0], current_tomato_position[1] + direction[1])
                next_row, next_col = next_position
                
                if is_ripenable(row=next_row, col=next_col, map = map) is False:
                    continue
                non_ripen_tomatoes.appendleft(next_position)
                map[next_row][next_col] = 1
                ripen_tomato_count += 1
        day += 1

    if ripen_tomato_count == total_tomato_count:
        return day
    else:
        return -1

line = sys.stdin.readline().split(' ')
m = int(line[0])
n = int(line[1])
map = [[int(x) for x in sys.stdin.readline().split(' ')] for x in range(n)]
print(solution(m = m, n = n, map = map))

 

파이썬 연습용으로 풀어본 문제.

오랜만에 익숙하지 않은 언어로 풀었는데 생각보다 금방 풀었다.