[백준][DP] 1005번 ACM Craft

문제

건물 순서 규칙이 주어지고, 해당 규칙에 맞춰서 건물을 지을 때 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1005)

풀이

처음엔 BFS를 써서 풀어봐야겠다! 라고 생각을 했는데 먼저 풀어본 친구가 BFS를 쓰면 시간초과가 난다고 알려주어서 고민을 했던 문제입니다. 그리고 떠오른 것은 topological sort였습니다. topological sort는 어떠한 사건이 선행되어야 다음 사건을 진행할 수 있는 관계들이 주어질 때 활용할 수 있는 방법입니다.(이후에  topological sort라는 포스팅을 통해 자세히 다뤄보도록 하겠습니다.) 이 문제에서도 2번, 3번 건물을 무조건 지어야 4번 건물을 지을 수 있는 이런 선행되어야 다음이 행해지는 관계들이 주어집니다. topological sort을 하기 위해 DFS를 구현했는데 이 부분에서도 topological sort의 정의를 완벽히 파악하지 못하고 있어서 결과를 만들어내기까지 조금 시간이 걸렸습니다. DFS를 통해서 노드들을 순회한 다음 해당 순서를 거꾸로 하면 원하는 topological sort 결과가 만들어집니다. 이렇게 되면 sort 된 노드들의 순서는 무조건 먼저 지어야하는 건물이 앞에 있게 됩니다. 따라서 이를 통해서 dp값을 채워나갈 수 있습니다. DFS의 순회순서를 stack에 넣어놓은 다음 하나씩 pop하며 해당 node까지 건물을 짓기위한 최소의 시간을 구합니다. 하나의 컴포넌트가 시작되는 노드일 경우에는=이전에 어떠한 건물이 지어지지 않았어도 지을 수 있는 경우엔 dp의 값은 자신의 건물을 세우는 시간입니다. 그 다음은 인접리스트를 통해서 어떠한 노드 i에서 어떠한 노드 j로 갈 수 있다면 dp[i]를 이용해 j의 값을 갱신시켜 나갑니다. j로 갈 수 있는 모든 i들의 건설시간을 확인하고 그 중 가장 많이 필요로 하는 시간이 j를 건설하기 위한 최소한으로 필요한 시간입니다. topological sort+dp를 적절히 사용해야 풀 수 있는 어려운 문제입니다!

코드

https://github.com/kswim/Algorithm/blob/master/DP/1005.cpp