chldntjr1211   5년 전

게시판에 있는 반례들을 다 찾아서 시도해보고 혼자 여러가지 생각해봤지만 

늪에 빠져버린 듯합니다. 반례가 눈에 잘 안보이네요.

0인 차수들의 노드들을 큐에서 꺼내고 다음 의존성이 있는 모든 노드들을 돌면서

cache[there] = Max(cache[prev]+buildTime[there])  기능을 수행하게 끔 만들었습니다.

제가 문제에서 제가 캐치하지 못한 포인트나 코드 상의 실수가 있을까요?

chldntjr1211   5년 전

cache[here] += buildTime[here]; 이 부분에서 계산이 중복이 된 것 같네요.

값을 초기화하고 최고값을 가진 이전 캐시에 here의 건설시간을 더해서 캐시를 완성하려고 했는데..  하지만 반례를 찾진 못했습니다. 

방향 그래프에서 나타날 수 있는 역방향 간선을 제외한 모든 간선 종류에 대해선 작동을 하고 여러 개의 루트가 동시에 시작되는 경우들에도

잘 작동했거든요.

테스트케이스를 뜯어볼 수 있고 ㅠㅠ 반례가 너무 궁금한데 혹시 눈에 띄시는 분은 댓글 남겨주세요.

캐시값을 해당 노드의 건설시간으로 초기화하고 

while(!q.isEmpty()){
    int here = q.poll();

    for (int i = 0; i < adj.get(here).size(); i++) {
        int there = adj.get(here).get(i);
        indegree[there]--;
        if(indegree[there] == 0) q.add(there);

        cache[there] = Math.max(cache[there], cache[here]+buildTime[there]);
    }
}

라고 정리하니 해결됐습니다. 


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