[백준] 7576 토마토 (파이썬 python)

 

문제 링크

 

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

7576번: 토마토

 

 

문제 풀이

 

전형적인 BFS 문제로 문제 조건을 잘 따라가다보면 해결할 수 있는 문제입니다.

 

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])
            visited[i][j] = 1

 

전체 배열을 입력받고 익은 토마토(1)일 경우 큐에 추가해주고 방문 처리를 해줍니다.

 

이 문제에서는 최종적으로 나올 수 있는 결괏값이 총 3가지입니다.

(1) 토마토가 모두 익을 때까지의 최소 날짜

(2) 처음부터 토마토가 모두 익어있었다면 1

(3) 토마토가 모두 익을 수 없다면 0

 

이를 분리하기 위해 flag라는 변수를 생성하고 상태를 저장하고자 했습니다.

flag = 1
# 처음부터 모든 토마토가 익어있었을 경우
if len(queue) == m * n:
    flag = 0
    
# 처음에 모든 토마토가 익은 상태가 아니었을 경우에 대해서만 실행
if flag:
    while queue:
        x, y = queue.popleft()
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = 1
                if graph[nx][ny] == 0:
                    queue.append([nx, ny])
                    graph[nx][ny] = graph[x][y] + 1
    for i in range(n):
        max_val = max(max_val, max(graph[i]))
        # bfs가 끝났음에도 익지 않은 토마토(0)가 남아있을 경우
        if 0 in graph[i]:
            flag = -1
            break

# 정상적으로 최소 날짜를 출력할 경우
if flag > 0:
    print(max_val - 1)
# 그 외의 경우 (모든 토마토가 익지 않았을 경우, 처음부터 모든 토마토가 익었을 경우)
else:
    print(flag)

 

 

전체 코드

 

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[0] * m for _ in range(n)]
queue = deque()
flag = 1
max_val = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])
            visited[i][j] = 1
if len(queue) == m * n:
    flag = 0
if flag:
    while queue:
        x, y = queue.popleft()
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = 1
                if graph[nx][ny] == 0:
                    queue.append([nx, ny])
                    graph[nx][ny] = graph[x][y] + 1
    for i in range(n):
        max_val = max(max_val, max(graph[i]))
        if 0 in graph[i]:
            flag = -1
            break
if flag > 0:
    print(max_val - 1)
else:
    print(flag)