[python] 백준 7576번 토마토

백준 7576번 토마토

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

문제

풀이

또 BFS. 그냥 나는 최단 / 최소 이런 문자가 있으면 BFS 로 풀기로 했다. 풀면서 미로탐색이 생각났다.
queue 에다 x, y, count 를 넣고 계속 count 를 업데이트 시켜나갔다.

from collections import deque

m, n = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

queue = deque()

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i,j,0))

def bfs():
    while queue:
        last_count = 0
        x,y,count = queue.popleft()

        if x-1 >= 0 and graph[x-1][y] == 0:
            graph[x-1][y] = 1
            queue.append((x-1, y, count+1))
        if x+1 < n and graph[x+1][y] == 0:
            graph[x+1][y] = 1
            queue.append((x+1, y, count+1))
        if y-1 >= 0 and graph[x][y-1] == 0:
            graph[x][y-1] = 1
            queue.append((x, y-1, count+1))
        if y+1 < m and graph[x][y+1] == 0:
            graph[x][y+1] = 1
            queue.append((x, y+1, count+1))
        
        last_count = count

    return last_count

result = bfs()

if any( 0 in value for value in graph):
    print(-1)
else:
    print(result)

📌 주의

• 이건 다른 bfs 문제들과 다르게 최종 도착점이 없다보니 if 목표 도착 시 count 반환이 안된다. 그래서 last_count 가 필요하고, 마지막에 업데이트된 count 를 리턴해줘야 한다.
• 그리고 인자로 뭘 넘겨줘야하는지를 항상 잘 생각해보자. 생각보다 문제가 단순할 수도...
• 리스트 안에 있는 숫자 확인하는 any 내장 함수 :

	numbers = [1,2,3,4,5]
    if any(number == 1 for number in numbers):
    	print('hi')
     numbers = [[1,2],[3,4,5]]
     # 이차원 리스트에서 특정 값이 있는지 확인할 때는 in 연산자를 사용하여 각 서브리스트를 검사한다.
     if any(1 in number for number in numbers):
     	print('hi')
     ```