blackco   1년 전

건물이 건축되는 시간을 역으로 계산했습니다. (역 DFS?) 다음은 알고리즘에 대한 설명입니다. 

가장 마지막으로 건축되는 건물W에 대해 timeOfConstruction[W] = time[W]로 시작하여

그 전 건축물의 건축시간을 timeOfConstruction[preW] = timeOfConstruction[W] + time[preW]으로 계산하였으며

필요건축물이 없는 건축물까지 계산하도록 하였습니다.  (A건축물 -> B건축물: A는 B의 필요건축물)

이 과정에서 특정 건물은 두 번이상 계산되는 경우가 발생하는데,(대표 예제의 1번 건축물//1->2->4 & 1->3->4: 2번 계산됨)

그러한 경우에는 기존값과 새로 계산되는 값 중 큰 쪽을 택했습니다. (critical pass의 개념으로 보면 될 거 같습니다.)

전체계산이 끝난 후 timeOfConstruction에 계산된 모든 값 중 가장 큰 값을 정답으로 택했습니다.


이렇게 했는데 며칠간 계속 틀렸다고 나오네요... 

 도움 부탁드립니다.. 감사합니다. 

djm03178   1년 전

한 번 방문한 후 간선을 모두 지워버리기 때문에 추후에 더 큰 시간으로 재방문했을 때 그 이후 정점에 도달하지 못합니다.

https://ideone.com/Q4uv1R

blackco   1년 전

미처 그부분까지 생각을 못했네요... djm03178님의 많은 답변을 보며 대단하시다는 생각을 했지만 헛점을 금방 찾아내시는 예리함에 재차 감탄합니다.

blackco   1년 전

이렇게 해서 틀린 문제는 해결했지만 다시 시간 초과가 뜨네요 ㅎㅎㅎ ㅠ 

이 부분은 다시 한 번 고민해봐야겠습니다...ㅎ 

아무튼 막혔던 문제는 해결됐으니 질문은 '해결'로 바꾸어두겠습니다! 

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