글 읽기 - 파이썬 dfs 시간초과

billy4293 1년 전 0

시간초과 이유를 모르겠습니다.

import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]

for i in range(n):
    data = list(map(int,input().split()))
    idx = 1
    while data[idx] != -1:
        x, y = data[idx],data[idx+1]
        idx+=2
        graph[data[0]].append((x,y))



def dfs(graph, v, visited):
    for i, d in graph[v]:
        if visited[i] == 0:
            visited[i] = visited[v] + d
            dfs(graph, i, visited)
    m = max(visited)
    return visited.index(m)

    
visited = [0] * (n+1)
i= dfs(graph, 1, visited)
max1 = max(visited)
visited = [0] * (n+1)
j = dfs(graph, 1, visited)
max2 = max(visited)

print(max(max1,max2))

gunbros 1년 전 0

24라인의 visited.index() 때문에 시간초과가 발생하는 것 같습니다.

최대 조건인 100000개의 정점이 주어졌을 때 dfs를 통해 100000개의 정점을 탐색하는 과정에서 index메소드로 인해 최악의 경우 visited의 길이인 100000 만큼 매번 탐색하게 됩니다.

그러면 O(100000 * 100000)가 되어 시간초과가 발생하는 것 같습니다.

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

문제

문제

출처

ICPC

파이썬 dfs 시간초과

billy4293 1년 전 0

gunbros 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말