2023.01.18 토마토 백준[파이썬]

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

7576번: 토마토

 

import sys
from collections import deque
input = sys.stdin.readline
def main():
    def bfs(discovered):
        nonlocal graph
        max_time = 0
        while discovered: # 가야하는 곳이 없으면 종료
            #print(discovered)
            pos = discovered.popleft() # bfs로 선입선출 구조
            if graph[pos[0]][pos[1]] == 0:
                continue
            next_pos = [[pos[0]+1,pos[1]],[pos[0]-1,pos[1]],[pos[0],pos[1]+1],[pos[0],pos[1]-1]] # 다음에 갈 수 있는 좌표
            for np in next_pos:
                if 0<= np[0] < N and 0<= np[1] <M and \
                    (graph[np[0]][np[1]] == 0 or (graph[pos[0]][pos[1]] + 1) < graph[np[0]][np[1]]): 
                #다음으로 가는 것이 범위 안에 있고 0보다 크면서 최단 길이가 더 짧게 갈 수 있을 때
                    discovered.append(np) # 가야하는 곳 추가
                    graph[np[0]][np[1]] = graph[pos[0]][pos[1]] + 1 # 그 곳에 시간 추가
                    if graph[pos[0]][pos[1]] + 1 > max_time:
                        max_time = graph[pos[0]][pos[1]] + 1
        return max_time

    M ,N = map(int,input().split()) # N,M 입력
    pos_list = deque()
    graph = [list(map(int,input().split())) for _ in range(N)] # 농장 입력
    for i in range(N): # 돌면서 1인 구간부터 bfs 실행
        for j in range(M):
            if graph[i][j] == 1:
                pos_list.append([i,j])
                
    max_time = bfs(pos_list)
    for i in graph: # 끝난 곳 돌면서 시간 체크
        if 0 in i: # 0 이 있으면 -1 리턴
            print(-1)
            return
    if max_time == 0:
        print(0)
    else: 
        print(max_time-1)        
    return
main()

이번 문제는 코드는 바로 짰는데 시간초과가 나서 한 3일 냅둔 문제... 풀다가 어디를 줄여야 할지 감도 안와서 백준에 질문을 올렸다 전 코드는 for문 안에서 1이라고 할 때마다 bfs를 돌렸는데 그부분이 때문에 시간초과가 난거 같다. 그리고 maxtime 구한다고 한번 더 돌렸었는데 조언을 받아서 bfs에서 한번에 maxtime 까지 구하게 만들었다. 지금 까지는 bfs 나 dfs 둘 다 따로 구현을 하고 탐색 이외에는 생각을 안했었는데 이번 기회에 함수를 짜도 이렇게 시간이 부족 한 거에서는 한번에 넣어야 한다고 생각했다. 첫 골드 문제여서 기분이 좋다.