백준 알고리즘 7576. 토마토

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

7576번: 토마토

 

전체 코드

처음 시도

class Solution:
    def __init__(self):
        self.queue = collections.deque()
        self.remain_count = 0
        self.day = 0

    def do(self, mat):
        w, h = len(mat[0]), len(mat)

        for y in range(h):
            for x in range(w):
                if mat[y][x] == 0:
                    self.remain_count += 1

        for y in range(h):
            for x in range(w):
                if mat[y][x] == 1:
                    self.queue.append((x, y))

        self.bfs(mat, w, h)
        if self.remain_count > 0:
            return -1
        return self.day

    def color_tomato(self, queue, mat, x, y, w, h):
        if 0 <= x < w and 0 <= y < h and mat[y][x] == 0:
            self.remain_count -= 1
            mat[y][x] = 1
            queue.append((x, y))

    def bfs(self, mat, w, h):
        while self.queue:
            for _ in range(len(self.queue)):
                x, y = self.queue.popleft()
                self.color_tomato(self.queue, mat, x + 1, y, w, h)
                self.color_tomato(self.queue, mat, x - 1, y, w, h)
                self.color_tomato(self.queue, mat, x, y - 1, w, h)
                self.color_tomato(self.queue, mat, x, y + 1, w, h)
            if len(self.queue) > 0:
                self.day += 1


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

mat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

print(Solution().do(mat))

 

 

2차원 배열을 순회하며, 가장 먼저 익지 않은 토마토의 개수를 모두 센다. 마지막에 익지 않은 토마토가 남아있다면 -1 처리를 하기 위해 존재한다.

이후 2차원을 순회하며, 익은 토마토를 큐에 저장한다. 이후 큐의 길이만큼 dequeue를 진행하며 상,하,좌,우의 토마토에 익지 않은 토마토를 확인하여 익지 않은 토마토 개수를 -1하고, 해당 x, y, 좌표를 익게 만든 후 큐에 enqueue한다. 

상하좌우 확인이 완료된 이후에 큐에 데이터가 있다면 토마토를 하나 이상 익게 했다는 뜻이므로 시간에 1일을 증가시킨다.

결과에 익지 않은 토마토 개수가 남아있다면 -1을 반환하고 그렇지 않으면 걸린 시간을 반환한다.

 

해설 코드

from collections import deque

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

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

 

일반적인 BFS를 진행하면서 각 step별로 익은 곳의 값을 +1 진행하여 matrix의 각 값을 익은 날짜로 설정할 수 있다. BFS가 완료된 후 2차원 배열을 순회하면서 최대 날짜를 반환한다. 시간은 1부터 시작하므로 결과에 -1를 해준다. 만약 익지 않은 토마토 0이 존재하면 -1을 반환한다.