7576번 토마토

문제 설명

7576번: 토마토

 

나의 풀이

from collections import deque


def bfs(graph, q):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while q:
        y, x = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<len(graph[0]) and 0<=ny<len(graph) and not graph[ny][nx]:
                graph[ny][nx] = graph[y][x] + 1
                q.append((ny, nx))

    return graph

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

result_graph = bfs(graph, q)

def solution(result_graph):
    answer = 0
    for i in range(len(result_graph)):
        for j in range(len(result_graph[0])):
            if not result_graph[i][j]:
                return -1
            else:
                answer = max(answer, result_graph[i][j])

    return answer - 1

print(solution(result_graph))

 많이 복잡해 보인다. bfs 문제라 쉽게 생각했지만, 약간의 함정이 있었다. 나의 경우 bfs startnode를 어떻게 동시적으로 시작해야하는지 고민에 빠졌었다. 하지만 q에 애초에 시작해야할 노드들을 넣고 bfs함수를 시작하면 된다. 그럼 내가 생각한 동시에 익은 토마토에서 시작할 수 있었다. 

 잘 생각해보면 bfs 원리를 생각할 때, 시작 노드에서 다음 노드들이 같은 거리로 확인이 되는데, 애초에 시작 노드들을 큐에 넣어주면 같은 원리로 동시에(?) 내가 생각한 대로 접근할 수 있다. 이해는 갔는데 글로 설명하기가 어렵다. 한번 다시 머리 속으로 정리해봐야겠다. 

 

1) 시작해야할 익은 토마토들의 위치 정보를 q에 넣어준다.

2) bfs함수에는 그래프와 시작 노드들의 위치 정보가 담긴 리스트를 매개변수로 넣는다. 

3) 시작 노드들로부터 익어가는 토마토들의 일자 정보를 만들어준다. 

4) 토마토 들의 익은 일자가 담긴 그래프가 만들어지고 이를통해 0이 있다면, 리턴 -1

0이 없다면 가장 큰 값에서 -1 해준 값이 해가 된다.(애초에 안익은 토마토 없어도 최대가 1이기에 -1하면 0이된다.)