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

woaksths 2년 전 0

dfs 랑 dp 이용해서 풀었습니다.

모든 노드를 root 노드라고 가정하고, 완전 탐색 돌려서 문제를 풀었습니다.

혹시 시간 초과가 나는데, 개선 가능한 부분 알려주시면 감사드리겠습니다!

import sys

def dfs(node):
    visited[node] = True
    for info in trees[node]:
        next_node = info[0]
        edge = info[1]
        if visited[next_node]:
            continue
        dp[next_node] += (dp[node] + edge)
        visited[next_node] = True
        dfs(next_node)

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    trees = {idx:[] for idx in range(N+1)}
    for _ in range(N):
        arrs = list(map(int, sys.stdin.readline().strip().split(' ')))
        start_node = arrs[0]
        for idx in range(1, len(arrs[:-1]), 2):
            next_node = arrs[idx]
            edge = arrs[idx+1]
            trees[start_node].append((next_node, edge))

    result = -1
    for idx in range(1, N+1):
        visited = [False for _ in range(N+1)]
        dp = [0] * (N+1)
        dfs(idx)
        result = max(result, max(dp))
    print(result)

snrnsidy 2년 전 1

생각하신 방법으로는 어떻게든 시간 내에 통과하는 건 불가능입니다.

woaksths 2년 전 0

감사합니다. 좀 더 고민해봐야겠네요!

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

문제

문제

출처

ICPC

파이썬 시간 초과ㅠ

woaksths 2년 전 0

snrnsidy 2년 전 1

woaksths 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말