목록업그레이드필요 (1)
멍
Q1005 ACM Craft
위상정렬 이라는 개념을 알아야 한다고 한다. 모르고 처음 푼 코드를 올린다. 그냥 dfs로 스택에 담아서 쭉 둘러보는 방법으로 옛날에 dfs풀었던 방법을 적용해서 풀었다. 분명 기존알고리즘과는 다르기때문에 비효율적으로 짰을 것이다. 4를 짓기 위해선 2,3을 동시에 행할 수 있고, 3을 건설하는 동안 2는 이미 다 완성되어 결과에 영향을 미치지 않는다. 4를 지으려면 10+100+10 = 120초의 건설시간 필요 만약 이렇게 되어있고 4가 최종건물이라면 4에서 바라봤을때 2,3,5가 지어져야 하는데 어차피 5가 110초이므로 2,3은 볼 필요도 없다. 그러므로 5가 최종 건설시간이다. 라고 생각할 수도 있다. 2,3이 결과에 무의미하다 해서 넘어가서는 안된다. 1때문에 그래서 모든 노드를 한번은 탐색해서..
problem solving/backjoon online judge
2019. 7. 8. 14:38