[BOJ] 7576 / 토마토 / Python 파이썬

[BOJ] 7576 / 토마토 / Python 파이썬

[BOJ] 7576 / 토마토 / Python 파이썬

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

7576번: 토마토

 

풀이

이차원 배열에서 주어진 시작점으로 부터 주어진 규칙을 시행하는 문제였다.

 

처음에는 각각의 시작점에서 시행하는 경우가 동시에 발생 하는 것을 고려하지 못하고,

독립적으로 시행하게 구현하였더니 시간초과가 발생하였다.

 

BFS 로 각각의 시작점을 같은 단계에서 동시에 수행되도록 구현하였더니 통과하였다.

 

from collections import deque


def doneCheck():
    global M, N

    res = 0

    for n in range(N):
        for m in range(M):
            if maps[n][m] == 0:
                return -1
            res = max(res, maps[n][m])
    return res-1


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

maps = [0] * N

for n in range(N):
    maps[n] = list(map(int, input().split()))

dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]

dq = deque()

for n in range(N):
    for m in range(M):
        if maps[n][m] == 1:
            dq.append((n, m, 1))

            while dq:
                y, x, day = dq.popleft()

                for i in range(4):
                    Y = y + dy[i]
                    X = x + dx[i]

                    if 0 <= Y < N and 0 <= X < M:
                        if maps[Y][X] == -1:
                            continue
                        if maps[Y][X] and maps[Y][X] <= day:
                            continue

                        if maps[Y][X]:
                            maps[Y][X] = min(day+1, maps[Y][X])
                        else:
                            maps[Y][X] = day+1
                        dq.append((Y, X, maps[Y][X]))

print(doneCheck())

 

※ 문제와 문제를 해결하기 위한 도구에 대해 아직까지 깊이 있는 이해가 부족한거 같다.

 

 

---

참고블로그

 

https://pacific-ocean.tistory.com/267

[백준] 7576번(python 파이썬)

• 시작점을 모두 queue 에 저장하고 시작하는 것을 참고하였다.