위상 정렬 (1) 썸네일형 리스트형 [BOJ] 1005 ACM Craft 문제: https://www.acmicpc.net/problem/1005 위상 정렬의 대표격인 건설 순서 문제이다. 그런데 사실 난이도가 아주 없는 문제는 아니어서 이게 왜 1005번에 있나 조금 의심이 들기는 하는 부분이다. 사실 습격자 초라기에 비할 바는 못되지만... 하여튼 내 풀이를 설명하자면, DFS를 이용해 그래프를 순회하면서 함수가 종료할 때마다 저장하면 위상 정렬의 역순이 된다는 점을 이용해서 DP를 돌리는 방법으로 문제를 풀었다. 이를 위해서 순방향 간선과 역방향 간선의 인접 리스트를 별도로 만들었고, 역방향 간선의 인접 리스트의 크기가 0인 것들을 모두 DFS 돌리고 reverse해서 위상 정렬을 찾은 다음 그걸 역방향 간선 인접 리스트를 통해 바텀업 DP로 돌려서 결과값을 찾아냈다. .. 이전 1 다음