[백준] 1005번, ACM Craft (JavaScript)

Algorithm

📌 문제 정보 : ACM Craft

• 문제 분류 : DP, 위상 정렬, 그래프 이론
• 문제 출처 : 백준 골드 3, ACM Craft

✅ 접근 과정

이 문제의 경우 목표로 하는 건물을 짓기 위해 선행되어야 건물들의 총 걸리는 시간을 구하는 위상 정렬 문제이다.

위상 정렬이란?

위상 정렬이란 어떤 일을 하는 순서를 찾는 알고리즘으로 방향성이 존재하며 사이클이 없는 그래프에서 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 정렬을 말한다.

이 문제에서는 건물들의 선행 순서를 그래프로 나타낼 수 있고 목표로 하는 건물을 짓기 위해 필요한 선행 건물들의 순서와 비용을 구해야 하기에 위상 정렬을 사용해야 하는 문제였다.

풀이 방법

1. 각 테스트 케이스에서 건물들의 선행 순서에 대한 그래프와 위상 정렬에 필요한 선행 건물의 개수를 입력 받는다.
2. 선행 개수가 0인 건물들을 시작으로 위상 정렬을 실시하여 현재 DP 비용 < (선행 건물의 DP 비용 + 현재 건물을 짓는 비용) 큰 경우 DP 값을 더 큰 비용으로 갱신해준다.
3. 목표로 한 건물의 DP를 출력한다.

✨ 풀이 코드

🚩 마치며

위상 정렬.. 많이 들어봤지만 실제로 사용해 본 적은 이번이 처음이었다.

DFS, BFS의 경우 선행 조건이 생기면 탐색 중 변화된 값을 갱신해주기 위해 이전에 계산한 내용을 다시 업데이트 해줘야 하는 문제가 발생한다. 이를 해결하기 위해 위상 정렬을 쓸 수 있다는 것을 알게 되었다.

🎁 홍보

백준 풀이를 도와주는 크롬 익스텐션 : 백준 헬프(Baekjoon Help) 크롬 웹 스토어