[백준 7576번 python] 토마토 문제

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

7576번: 토마토

 

 

 

지금까지 BFS 문제를 풀때 하나의 시작점에서 출발해 문제를 푸는 방식이였다면 이번 문제는 두군데 시작부터 그 이상의 시작점을 통해 탐색을 진행하는 문제였습니다.

 

처음에는 이중포문을 통해 1인 시작점을 구하고 그 좌표를 함수로 전달해서 탐색하는 방법으로 구현하려 했으나 

하나의 시작점이 전달되었을때 바로 모든 값이 변경돼 다른 시작점이 투입되도 결과가 변경되지 않는 문제가 발생했습니다. 

 

두 번째 개선때 좌표값을 함수에 전달하는 방식이 아닌 큐에 시작점의 좌표를 넣고 BFS 함수에서 곧바로 탐색을 시작하면 하나의 시작점에서 탐색하듯이 시행될 수 있었습니다.

 

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

m,n = map(int, input().split())
box = []
result = -2
for _ in range(n):
    box.append(list(map(int,input().split())))

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

q = deque()

def bfs():
    while q:
        a,b=q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx <n and nx >=0 and ny <m and ny >=0 :
                if box[nx][ny] == 0:
                    box[nx][ny] = box[a][b] + 1
                    q.append((nx,ny))
       
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            q.append((i,j))

bfs()
check = 0
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            box[i][j] = -1
            check += 1
        result = max(result,box[i][j])
        
if check != 0:
    print(-1)
else:
    print(result-1)

 

알게된 점

일차원 리스트는 max()를 통해 최댓값을 바로 출력할 수 있지만, 이차원 리스트의 경우는 실행 되지않아 하나하나 비교하며 result 값을 갱신시키는 방식으로 해결했습니다.