★BOJ/1005_ACM Craft

[문제]

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

[처음 생각]

힌트가 위상정렬인걸 보고 일단 위상정렬을 찾아봤다... 

찾아보니 위상정렬 알고리즘은 여러 일들에 순서가 정해져있을 때 순서에 맞게 나열할 때 사용하는 알고리즘이어서 이 문제처럼 건설 순서가 정해져있고 순환이 없는 그래프이므로 사용하기 적절한 듯 하다.

위상정렬 알고리즘을 그대로 사용하되 중간에 max 값 갱신해주는 부분만 넣어주면 되지 않을까?!

[풀이]

위의 방법처럼 하려고 했는데 위상정렬을 짜려니 길어져서 혹여나 다른 방법으로 할 수 있을까 찾아보니 DP 재귀로 한 사람이 있었다. 

위상정렬을 하면 나중에 의존관계를 고려해야 하는데 DP로 풀면 의존관계를 고려하지 않고 거꾸로 지어야 할 마지막 건물번호를 기준으로 진입차수를 밟아나가며 올라가는 방식으로 풀었다(근데 이 사람은 굳이 왜 dp 배열을 썼는지 의문. 사용안했는데 필요없는데?!)

-> 이렇게 하니 시간 초과 떴다 ㅎ 역시 자바...

다른 풀이를 보니 위상정렬을 굳이 하지 않고 DFS로 돌리는 방식을 사용했다. 

-> http://fresh-man-s.blogspot.kr/2016/06/httpswww.html

---

위에서 시간초과가 나서 위상정렬 방식으로 하되 중간에 max값을 계속 갱신해주는 방식으로 풀었다. 

예제에 있는 테스트케이스 2개를 모두 확인했을 때, 하나하나 중간과정 따졌을 때 다 맞다고 생각했는데 다른 테스트 케이스를 틀렸나 보다...

나는 중간에 max 변수값을 계속 갱신하는 방식으로 풀었는데, 밑에서 위상정렬을 사용해서 푼 코드를 보면 dp 배열로 현재 노드까지에 대한 답을 계속 구해나가는걸 봤는데, 블로그는 나처럼 그래프를 단순 2차원 배열로 나타내지 않고 한 노드에 대해 연결된 간선을 나타냈다.

이런식으로...

근데 이건 C++에서만 되고 자바에서는 push_back을 구현해야 한다. -> 찾아봤을 때 비슷하게 LinkedList에서 push_after??과 같다고 하는데 다르다 ㅜㅜ 저건 한 노드에 대해 연결된 노드들을 담은 Vector를 저장해주는것과 같아서...

-> 결국 틀린 이유 이해 못함 

-> 틀린이유는 위상정렬한 단계별 결과들에서 나는 항상 max값을 찾아서 단순히 더해왔는데, 이 단계들의 선택된 정점들이 이어지는 경로는 아니어서 반례에서 틀린것

그래서 그 전의 max값을 가진 정점과 그 다음 따져지는 전입차수가 0인 정점이 연결되면 max값을 갱신하고 아니면 그냥 위상정렬만 진행하는 방식으로 하려는데 계속 안됨ㅎ...

-> 이렇게 해결해봤다. 역시 이런경우의 테스트케이스만 해결했을뿐이고 다른 테스트케이스는 또 틀림 ㅎ

[참고]

DP 재귀(위상정렬 사용 X)

http://algoshipda.blogspot.kr/2016/02/boj-1005-acm-craft.html

위상정렬 사용

http://xoding.tistory.com/45

[Code]

DP 재귀(위상정렬 사용 X)

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1005/ACMCraft2.java

위상정렬(틀림)

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1005/ACMCraft.java