BOJ#1005_ACM Craft

* 문제

https://www.acmicpc.net/problem/1005

* 풀이

건물 X를 지은 다음에 건물 Y를 건설할 수 있다.

어떤 일에 선, 후 관계/순서가 있으므로 위상정렬을 이용해보았다.

- 위상정렬 설명

http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824

Queue<Integer> q = new LinkedList<Integer>(); // indegree가 0인 노드들을 Queue에 넣는다. for (int i = 1; i <= N; i++) { if (indegree[i] == 0) { q.offer(i); cost[i] = D[i]; } } // N번 Loop : 노드가 N개이고 loop 1번에 노드가 1개씩 처리될 것이다. for (int i = 0; i < N; i++) { if (q.isEmpty()) { return; } int v = q.poll(); for (int nextNode : XY.get(v)) { // indegree가 0인 노드들을 제거하면서, 인접한 노드들의 indegree를 1씩 줄여준다. indegree[nextNode]--; // 인접한 노드들의 cost를 갱신해준다. if (cost[nextNode] < cost[v] + D[nextNode]) { cost[nextNode] = cost[v] + D[nextNode]; } // 인접한 노드의 indegree가 0이 되면 Queue에 삽입한다. if (indegree[nextNode] == 0) { q.offer(nextNode); } } } System.out.println(cost[W]);

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231005_ACMCraft