[Python] 백준 풀기 7576 - 토마토

파이썬 백준 7576번

골드5

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

7576번: 토마토

 

 

 

 

 

문제 보기

분류: 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

문제 풀기

BFS 를 사용하여 해결하는 문제이다.

익은 토마토의 위치 좌표를 2차원 deque() 로 먼저 저장을 한다.

popleft() 를 통하여 첫 번째 익어있는 토마토의 위치들과 지속적으로 익어가는 토마토의 위치를 순차적으로 꺼내어 모든 매트릭스(그래프)를 탐색할 때까지 반복한다.

이웃하여 다음날 익게 되는 토마토에는 그 이전의 토마토 (첫 토마토는 1) 에 계속 +1을 하여 누적 숫자를 저장한다.

모든 위치에 대해 탐색이 끝나면 matrix 안의 최댓값을 찾아 -1 (첫 토마토 지정 숫자)을 해준 뒤 출력하여 최소 날짜 result 를 얻는다. 만약 모두 0이면 result = -1.

 

 

함수 fnBFS() 안의 while que: 가 도는 동안 매번 deque 와 matrix 에서 변화되는 값을 가시적으로 확인해 보면 위와 같다.

(예제 입력 3)

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
from collections import deque

def fnWhereIsTomato(N, M, matrix):
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                que.append([i, j])

def fnBFS():
    while que:
        # print(que)          # print test
        # print(matrix)           # print test
        x, y = que.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                que.append([nx, ny])


if __name__ == "__main__":
    M, N = map(int, inputdata().split())
    matrix = [list(map(int, inputdata().split())) for _ in range(N)]
    
    que = deque([])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    fnWhereIsTomato(N, M, matrix)
    
    fnBFS()
    
    result = max(map(max, matrix)) - 1
    for row in matrix:
        for tom in row:
            if tom == 0:
                result = -1
    
    print(result)

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline
from collections import deque

def fnWhereIsTomato(N, M, matrix):
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                que.append([i, j])

def fnBFS():
    while que:
        print(que)          # print test
        print(matrix)           # print test
        x, y = que.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                que.append([nx, ny])


if __name__ == "__main__":
    M, N = map(int, inputdata().split())
    matrix = [list(map(int, inputdata().split())) for _ in range(N)]
    
    que = deque([])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    fnWhereIsTomato(N, M, matrix)
    
    fnBFS()
    
    result = max(map(max, matrix)) - 1
    for row in matrix:
        for tom in row:
            if tom == 0:
                result = -1
    
    print(result)



# 6 4
# 1 -1 0 0 0 0
# 0 -1 0 0 0 0
# 0 0 0 0 -1 0
# 0 0 0 0 -1 1

# deque([[0, 0], [3, 5]])
# [[1, -1, 0, 0, 0, 0], [0, -1, 0, 0, 0, 0], [0, 0, 0, 0, -1, 0], [0, 0, 0, 0, -1, 1]]
# deque([[3, 5], [1, 0]])
# [[1, -1, 0, 0, 0, 0], [2, -1, 0, 0, 0, 0], [0, 0, 0, 0, -1, 0], [0, 0, 0, 0, -1, 1]]
# deque([[1, 0], [2, 5]])
# [[1, -1, 0, 0, 0, 0], [2, -1, 0, 0, 0, 0], [0, 0, 0, 0, -1, 2], [0, 0, 0, 0, -1, 1]]
# deque([[2, 5], [2, 0]])
# [[1, -1, 0, 0, 0, 0], [2, -1, 0, 0, 0, 0], [3, 0, 0, 0, -1, 2], [0, 0, 0, 0, -1, 1]]
# deque([[2, 0], [1, 5]])
# [[1, -1, 0, 0, 0, 0], [2, -1, 0, 0, 0, 3], [3, 0, 0, 0, -1, 2], [0, 0, 0, 0, -1, 1]]
# deque([[1, 5], [3, 0], [2, 1]])
# [[1, -1, 0, 0, 0, 0], [2, -1, 0, 0, 0, 3], [3, 4, 0, 0, -1, 2], [4, 0, 0, 0, -1, 1]]
# deque([[3, 0], [2, 1], [0, 5], [1, 4]])
# [[1, -1, 0, 0, 0, 4], [2, -1, 0, 0, 4, 3], [3, 4, 0, 0, -1, 2], [4, 0, 0, 0, -1, 1]]
# deque([[2, 1], [0, 5], [1, 4], [3, 1]])
# [[1, -1, 0, 0, 0, 4], [2, -1, 0, 0, 4, 3], [3, 4, 0, 0, -1, 2], [4, 5, 0, 0, -1, 1]]
# deque([[0, 5], [1, 4], [3, 1], [2, 2]])
# [[1, -1, 0, 0, 0, 4], [2, -1, 0, 0, 4, 3], [3, 4, 5, 0, -1, 2], [4, 5, 0, 0, -1, 1]]
# deque([[1, 4], [3, 1], [2, 2], [0, 4]])
# [[1, -1, 0, 0, 5, 4], [2, -1, 0, 0, 4, 3], [3, 4, 5, 0, -1, 2], [4, 5, 0, 0, -1, 1]]
# deque([[3, 1], [2, 2], [0, 4], [1, 3]])
# [[1, -1, 0, 0, 5, 4], [2, -1, 0, 5, 4, 3], [3, 4, 5, 0, -1, 2], [4, 5, 0, 0, -1, 1]]
# deque([[2, 2], [0, 4], [1, 3], [3, 2]])
# [[1, -1, 0, 0, 5, 4], [2, -1, 0, 5, 4, 3], [3, 4, 5, 0, -1, 2], [4, 5, 6, 0, -1, 1]]
# deque([[0, 4], [1, 3], [3, 2], [1, 2], [2, 3]])
# [[1, -1, 0, 0, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 0, -1, 1]]
# deque([[1, 3], [3, 2], [1, 2], [2, 3], [0, 3]])
# [[1, -1, 0, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 0, -1, 1]]
# deque([[3, 2], [1, 2], [2, 3], [0, 3]])
# [[1, -1, 0, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 0, -1, 1]]
# deque([[1, 2], [2, 3], [0, 3], [3, 3]])
# [[1, -1, 0, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 7, -1, 1]]
# deque([[2, 3], [0, 3], [3, 3], [0, 2]])
# [[1, -1, 7, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 7, -1, 1]]
# deque([[0, 3], [3, 3], [0, 2]])
# [[1, -1, 7, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 7, -1, 1]]
# deque([[3, 3], [0, 2]])
# [[1, -1, 7, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 7, -1, 1]]
# deque([[0, 2]])
# [[1, -1, 7, 6, 5, 4], [2, -1, 6, 5, 4, 3], [3, 4, 5, 6, -1, 2], [4, 5, 6, 7, -1, 1]]

# 6