글 읽기 - 50%에서 틀렸습니다가 나옵니다. 혹시 문제점을 찾아주실수 있나요?ㅠㅠ

hjy5405 3년 전 0

해당 건물을 짓기 전

prerequisite에 해당하는 건물들의 비용 중 최대인 비용에

해당 건물의 비용을 더하여 해당 건물을 짓는데 필요한 최종 비용을 구하는 식으로

계산했었습니다.

prerequisite이 없는 건물부터 queue에 삽입하여

queue에서 꺼낸 건물 번호의 비용을 업데이트하고,

prerequisite이 모두 탐색된 건물 번호를 enqueue하는 식으로 진행하였습니다.

많은 테스트 케이스와 질문 답변에 있는 반례들에 대하여

올바른 답을 출력하는 것을 확인하였는데, 50% 정도에서 원인모를 틀렸습니다가 계속 출력되어

질문을 드려보고 싶었습니다.

혹시 문제점이나 발견하지 못했던 반례의 예시가 있을까요?

import sys

t = int(input())

for epoch in range(t):
    n, k = map(int, input().split())
    
    inedge = [0] * (n+1) # 각 node로 들어오는 edge의 개수를 저장
    inedge[0] = -1
    queue = [] # 들어오는 edge가 없는 node(prerequisite 모두 다 본 경우)를 저장하는 큐
    cost = [0] + list(map(int, input().split())) # 각 node 번호의 건설 시간
    result = [0] * (n+1) # 각 node 번호를 짓는데 총 걸리는 최단 시간
    pre = []
    post = []
    
    for i in range(n+1):
        pre.append([])
        post.append([])
        
    for i in range(k):
        a, b = map(int, sys.stdin.readline().split())
        pre[b].append(a) # node의 prerequisite 목록 저장
        post[a].append(b) # 이 node가 어떤 node의 prerequisite 인지 저장
    
    goal = int(input()) # 목표 건물 번호
        
    for i in range(1, n+1):
        inedge[i] = len(pre[i]) # inedge 개수 초기화

    while(True):
        if inedge[goal] != 0:
            for i in range(1, n+1):
                if inedge[i] == 0: # inedge = 0 인 node enqueue(위상정렬 queue이용 방법 응용)
                    queue.append(i)
        
            if len(queue) == 0:
                break
            node = queue.pop(0)
        else: node = goal # goal의 prerequisite들에 대해 모두 검사한 경우 해당 건물비용 바로탐색
        
        max_cost = 0 # prerequisite 들 중 가장 큰 cost 저장할 변수
        for pre_node in pre[node]:
            if result[pre_node] > max_cost:
                max_cost = result[pre_node]
        result[node] = max_cost + cost[node] # 해당 건물 비용과 max_cost 더한 비용합으로 최종 비용 산출
        
        if node == goal: # 목표 node에 대한 결과 구했을 경우 반복문 종료
            break
        
        inedge[node] = -1 # 방문한 node에 대한 marking
        for i in post[node]: # 해당 node가 prerequisite으로 사용되었던 node들의 inedge 1 감소
            inedge[i] -= 1
        
    print(result[goal])

qktkzpal3301 3년 전 3

30~33번 라인에 의해서, 큐에 엄청나게 많은 원소가 적재되어, 불필요하게 많은 루프를 진행하게 될 수 있습니다.

1~50000번째 건물이 모두 indegree가 0이고, 50001번째 건물이 prerequisite을 50000번째 건물로 갖으며, W(문제에서 요구하는 건물)가 50001번째 건물을 prerequisite으로 갖는다고 할 때, 첫 while루프에 50000개의 원소가, 두번째에 49999개....이런식으로 엄청나게 많은 원소가 큐에 쌓이게 됩니다. 그리고 50000번째 원소를 큐에서 빼내게 되어도 이미 큐에 엄청나게 많은 원소가 적재되었기 때문에 50001번째 건물은 큐를 모두 비우고 나서야 연산을 수행할 수 있습니다.

51~52번라인의 indegree를 감소시키는 연산과 동시에 큐에 원소를 삽입하는 식의 방법은 어떨까요?

hjy5405 3년 전 1

와 그렇게 바꾸니깐 바로 해결되었습니다. 딱 정확한 포인트를 집어주셨네요 정말 감사합니다. ㅠㅠ

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

문제

문제

출처

ICPC

50%에서 틀렸습니다가 나옵니다. 혹시 문제점을 찾아주실수 있나요?ㅠㅠ

hjy5405 3년 전 0

qktkzpal3301 3년 전 3

hjy5405 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말