[BaekJoon] 백준 7576번 토마토 - Python

[BaekJoon] 백준 7576번 토마토

 

🎈문제

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

7576번: 토마토

 

💬설명

• 비슷한 문제를 여러개 풀어봤기 때문에 금방 풀었다.
• Bfs로 많이 푼 것 같은데, 큐를 쓰지 않고 풀었다. 아래와 같이 푸니까 pypy로 채점하지 않고 제한시간을 만족시킬 수 있었다.
• 아래와 같이 푼다.
  • 토마토 위치를 먼저 배열에 저장해준다.
  • 익은 토마토 개수와 모든 토마토 개수를 따로 저장해준다. (나중에 일일히 세지 않고 다익었는지 체크해주기 위해)
  • 이제 while문으로 하루하루 토마토가 퍼져가는 과정을 구현해준다.
    • 4개 방향의 토마토가 익으면 익은 토마토 개수를 update해주고 새로운 토마토 배열에 추가해준다.
    • 만약 하루가 지난 직후 익은 토마토 개수와 다음 날 넘어가기 직전 익은 토마토 개수가 같다면 하루 사이에 어떤 토마토도 익지 않았다는 의미이므로 더이상 토마토가 익을 수 없어 -1을 출력하고 종료한다.
    • 토마토 배열을 새로운 토마토 배열로 바꿔주고 다음날로 넘어간다. (어차피 기존 토마토 배열의 토마토는 4방향 모두 익었기 때문에 다음날 고려해줄 필요가 없다.)
    • 예외) 만약 처음 입력부터 모든 토마토가 다 익었을 경우를 먼저 처리해준다.

 

👩‍💻코드

M, N = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
arr = []
tomato = []
after = 0  # 익은 토마토
all = 0  # 모든 토마토
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 1:
            tomato.append([i, j])
            after += 1
            all += 1
        elif arr[i][j] == 0:
            all += 1

# 이미 다 익었을 경우
if after == all:
    print(0)
    exit()

day = 0
while True:
    day += 1
    after_b = after
    new_tomato = []
    for t in tomato:
        for i in range(4):
            nx = t[0] + dx[i]
            ny = t[1] + dy[i]

            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            if arr[nx][ny] != 0:
                continue
            arr[nx][ny] = 1
            new_tomato.append([nx, ny])
            after += 1

            if after == all:
                print(day)
                exit()
    tomato = new_tomato
    if after_b == after:
        print(-1)
        exit()