분명 동적 계획법 기초에 있는 문제인데, 알고리즘 분류는 위상 정렬로 되어있다.
순간 보고 멘붕해서 위상정렬에 대해서 처음부터 공부했다..
물론 동적 계획법으로도 풀 수 있으나, 그 양이 방대해서 위상정렬로 푸는게 도움이 될 것 같다. 위상정렬에 대한 문제도 많으니 말이다.
위상정렬에 대해 따로 정보를 주자면, 이어져 있는 노드들을 순서에 따라 정렬하는 것이다.
자세한 내용은 나보단 더 설명이 잘 돼있는 블로그가 있으니 그 블로그 링크를 올리겠다.
http://kks227.blog.me/220620723528
어우 이분 설명 잘하신다 진짜
아무튼 위상정렬을 처음 해보는 나로써는 변수를 적어놓고 아 이걸 왜 적어줬지 어디다 쓰는거였지? 하고 계속 반복하게됐다.. 결국 풀긴 했지만 말이다...
일단 위상정렬이 됐다는 가정 하에,
만약 1번 노드가 끝났다면, 1번 노드와 이어져있는 모든 노드들의 최소 건설시간은 1번노드 + 자신노드 이다.
예시로 가져온 문제이다.
1번 노드와 연결돼있는 모든 노드들의 건설시간을 1번 노드만큼 더해준다. 1번 노드와 연결돼있는 노드는 2번, 3번 그러므로 2번, 3번의 현재 건설값은 11초와 110초이다.
4번이 건설되려면 연결돼있는 노드들중에서 가장 큰 값이 선택되어야 한다. 왜냐면 만약 2번을 다 건설했다하더라도 3번은 건설중일테니까
3번이 건설되기전까진 4번을 건설할 수 없다. 그래서 자신이 건설되려면 자신의 전 노드들중 가장 큰 값이 건설 값이 된다.
큰 건설값 + 자신의 값을 출력하면 완료!
<풀이 소스>
풀면서 이 변수가 뭐하는 변수였더라.. 하면서 뇌사가 좀 많이 왔다..
그래서 옆에 주석을 하나하나씩 다 적어줌...
