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]); } }
라고 정리하니 해결됐습니다.
chldntjr1211 5년 전
게시판에 있는 반례들을 다 찾아서 시도해보고 혼자 여러가지 생각해봤지만
늪에 빠져버린 듯합니다. 반례가 눈에 잘 안보이네요.
0인 차수들의 노드들을 큐에서 꺼내고 다음 의존성이 있는 모든 노드들을 돌면서
cache[there] = Max(cache[prev]+buildTime[there]) 기능을 수행하게 끔 만들었습니다.
제가 문제에서 제가 캐치하지 못한 포인트나 코드 상의 실수가 있을까요?