악곱 == 악성곱슬

BFS

---

해당 문제를 BFS로 풀게 된 이유는 다음과 같다.

• 가까운 토마토로 “익는 행위”가 전파 되므로 level-order로 보는 BFS가 편할 것이다 판단
• 여러 군데에서 시작하므로 시간 복잡도를 줄이기 위해 해당 좌표들을 queue에 넣어서 BFS로 풀어야 시간초과가 나지 않을 것이라는 판다

처음에는 이중 for문 안에 bfs를 넣어서 시간 초과가 났다. queue에 depth를 tuple형태로 넣어서 여러 시작점에서 동시에 bfs를 수행해도 되도록 구현했다.

코드는 아래와 같다.

import sys
from collections import deque

dx = [1, -1, 0, 0]  # 상, 하, 좌, 우
dy = [0, 0, -1, 1]

def get_max(graph):
    _max = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                return -1
            if _max < graph[i][j]:
                _max = graph[i][j]
    return _max - 1

def bfs(graph, start, n, m):
    queue = deque()
    for c in start:
        queue.append(c)   # 세로, 가로, 거리(깊이)
    while queue:
        cur_x, cur_y, depth = queue.popleft()
        # 네 방향 탐색
        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            # 인덱스 범위 밖이면
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            # 토마토가 없는 공간이라면
            if graph[nx][ny] == -1:
                continue
            # 이미 방문했던 토마토라면
            if graph[nx][ny] > 1:
                # 지금 상황이 해당 토마토 밭에 더 가까우면
                if graph[nx][ny] > depth + 1:
                    graph[nx][ny] = depth + 1
                    queue.append((nx, ny, depth + 1))
            # 처음 방문하는 토마토라면
            if graph[nx][ny] == 0:
                graph[nx][ny] = depth + 1
                queue.append((nx, ny, depth + 1))

def solution(graph, n, m):
    start = list()
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:    # (n, m)
                start.append((i, j, 1))
    bfs(graph, start, n, m)
    answer = get_max(graph)
    return answer

if __name__ == "__main__":
    M, N = map(int, sys.stdin.readline().rstrip().split())
    G = list()
    for _ in range(N):
        G.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(solution(G, N, M))