글 읽기 - 시간 초과에 대한 개선 및 위상 정렬 질문

zombie3 5년 전 0

~~게시판에 있는 반례를 찾아서 돌려보면 에러는 없는걸로 생각됩니다만... 문제는 시간 초과네요.~~

~~계속 시간 초과가 나다보니 코드를 제대로 짜고 있는지도 헛갈립니다. @,@~~

~~다른분들은 input 바꾸면 통과라고 하시던데 ㅠㅠ~~

~~코딩의 한계인지 20줄이었던 코드가 50줄 짜리가 되어도 해결이 안봐지네요.~~

자문 자답 하네요. 게시판을 보다가 0 과 관련된 내용(Code Line : 20)을 확인하고 수정하니

바로 통과하네요.

그래도 아직 1번 사항은 아직 궁금증이므로 답변을 기다리겠습니다. ㅎ

각설하고 질문드리면

아래에 작성된 코드(33 ~ 47)가 위상 정렬 코드가 맞을까요?
~~코드의 문제점이나 시간 개선 포인트가 있을 까요?~~

import sys
input = sys.stdin.readline

class stack():
    def __init__(self):
        self._l=[]
    def top(self):
        if len(self._l)==0: return -1
        else: return self._l[-1]
    def pop(self):
        if len(self._l)==0: return -1
        else: return self._l.pop()
    def empty(self):
        if len(self._l)==0: return True
        else: return False
    def push(self, data):
        self._l.append(data)

def build(p):
    if cache[p] == 0: cache[p] = max([0] + [build(x) for x in o[p]]) + d[p]
    return cache[p]

for _ in range(int(input())):
    n,k = [int(s) for s in input().split()]
    d = [0] + [int(x) for x in input().split()]
    cache = [0]*(n+1)

    o = [[] for _ in range(n+1)]
    for _ in range(k):
        x,y = [int(x) for x in input().split()]
        o[y].append(x)
    # 초기화 -----------------------------------
    c = [0]*(n+1)
    r = []

    w = int(input())
    s = stack()
    s.push(w)
    while not s.empty():
        x = s.pop()
        if c[x] == 1: continue
        r.append(x)
        c[x] = 1
        for y in o[x]:
            if c[y] == 0:
                s.push(y)
    # 위상 정렬? --------------------------------
    for i in r[::-1]: build(i)
    print(cache[w])
    # 빌드 -------------------------------------

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

문제

문제

출처

ICPC

시간 초과에 대한 개선 및 위상 정렬 질문

zombie3 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말