[Baekjoon Online Judge] 백준 7576번 토마토(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 7576번 토마토

(Python)

(글쓴날 : 2020.03.31)

 

---

* Baekjoon Online Judge, 백준 7576번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 7576번 토마토

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

---

2) 풀이 과정

1을 익은 토마토, 0을 안 익은 토마토,  -1을 빈칸이라 가정했을 때, -1, 0, 1이 들어있는 2차원 배열이 주어지고, 익은 토마토를 기준으로 하루마다 -1 즉, 빈칸을 제외한 왼쪽, 오른쪽, 앞, 뒤 네 방향으로 익어져갈 때 모든 토마토가 익을 때까지의 최소 날짜를 출력하는 문제입니다.

단, 주어질 때부터 이미 다 익어있었다면 0을 출력하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 합니다.

 

저의 경우, BFS를 적용하여 문제에 접근했고, 처음 토마토들이 주어졌을 때 익은 토마토가 여러 개일 수 있음을 고려하여 익은 토마토를 전부 큐에 미리 넣어놓고 너비 우선 탐색을 실시했습니다.

너비 우선 탐색 종료 후, 한 번 더 탐색하여 익지 않은 토마토가 있다면 -1을 출력했고, 날짜가 하루 만에 끝났다면 (날짜 -1), 그 외 나머지 경우는 (날짜 -2)를 출력하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
 
def BFS(ripedTomato):
    global tomatos, visit, dx, dy, days
    dq = deque()
 
    for tomato in ripedTomato:
        i, j = tomato
        dq.append((i, j))
    
    while len(dq):
        for i in range(len(dq)):
            x, y = dq.popleft()
 
            if not visit[x][y]:
                visit[x][y] = True
                if not tomatos[x][y]:
                    tomatos[x][y] = 1
 
                for way in range(4):
                    ii, jj = x + dx[way], y + dy[way]
                    
                    if ii < 0 or ii > N - 1 or jj < 0 or jj > M - 1 or tomatos[ii][jj] == -1:
                        continue
 
                    dq.append((ii, jj))
                    
        days += 1
 
 
M, N = map(int, input().split())
tomatos = [list(map(int, input().split())) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
days = 0
ripedTomato = []
 
for i in range(N):
    for j in range(M):
        if tomatos[i][j] == 1:
            ripedTomato.append((i, j))
 
BFS(ripedTomato)
 
for tomatoLine in tomatos:
    if tomatoLine.count(0):
        print(-1)
        exit()
if days == 1:
    print(days - 1)
else:
    print(days - 2)

---