글 읽기 - 파이썬 시간초과 어렵습니다 ㅠㅠ 2178번

hanabira207 2년 전 0

N,M으로 가는 모든 path를 계산하고,

len이 최소가 되는 값을 리턴하게 했는데

모든 path 계산때문에 시간초과가 나는걸까요 ㅠㅠ

중간에 stop 하고싶은데 그러면 최소인 경로가 안나올까봐 다 구하게 해놨는데요....

도움 주시면 감사하겠습니다 ㅠㅠ

import sys
from collections import deque

sys.setrecursionlimit(10**7)
N, M = map(int,sys.stdin.readline().split())
graph_miro = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(N)]

paths = []
dx = [-1, 1, 0, 0]
dy = [0, 0 , -1, 1]
    
def dfs2(graph, start, end, visited=[]):
    visited = visited + [(start[0], start[1])]
    graph_miro[start[0]][start[1]] = "#"

    if start == end:
        paths.append(visited)

    for i in range(4):
        nx = start[0] + dx[i]
        ny = start[1] + dy[i]

        if (0<=nx<N and 0<=ny<M and graph_miro[nx][ny] == 1):
            dfs(graph, (nx,ny), end, visited)
                
dfs2(graph_miro, (0,0), (N-1,M-1))
shortest_path = [len(paths[i]) for i in range(len(paths))]
print(min(shortest_path))
                
          

hsw0194 2년 전 1

dfs를 사용해서 최단경로를 찾으려하면 지수시간이 걸린다고 알고있습니다. (모든 경로를 다찾아야하고, 지금 찾은 경로보다 나중에 찾은 경로보다 더 돌아가고 시간이 오래걸릴수 있으므로 다 탐색을 해줘야하니)

저는 가중치가 동일한 그래프에서 최단 경로(최단 시간 포함) 문제는 bfs를 사용하고 있습니다.

hanabira207 2년 전 0

감사합니다. 각 탐색의 특성과 BFS에 대한 코드리딩을 거쳐서 BFS로 완성하였습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 어렵습니다 ㅠㅠ 2178번

hanabira207 2년 전 0

hsw0194 2년 전 1

hanabira207 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말