-
1976알고리즘/acmicpc 2015. 3. 29. 16:16
딱 보면 알고리즘에 배운 Floyd Warshall로 해결 할 수 있을 것 같지만
Floyd Warshall 알고리즘은 나중에 한 값이 이전에 한 값에 영향을 줄 수 있는 문제점이 있다.
즉 나중에 연결 한 선이 이전에 연결한 선까지 변경 할 수 있다는 말이다(말이 좀 어렵다. 그림으로 표현하면 쉬울것 같은데 그림 그리자니 그건 귀찮고)
그래서 내가 10달전에 제출해보았던 코드들은 대부분 Floyd 알고리즘을 썼더니 모두 틀렸다.
새롭게 생각해낸 방법은 다익스트라 알고리즘을 이용한 방식이다.
한 점을 루트 로 잡고 그 점으로 부터 bfs 탐색을 한다
여기서 bfs로 거쳐가는 노드들은 모두 루트로부터 연결이 가능한 노드들이다.
난 좀 무식하게 해서 모든 점을 루트로 잡아서 연결을 했다.
그러면 이건 나중에 연결한 선이 이전의 결과에 영향을 주지 않느냐고 반문 할 수 도 있다
하지만 아무리 새롭게 루트를 잡아도 이전에 연결된 트리구조에서 더이상 확장 되지 않기 때문에 새로운 노드를 발생할 가능성은 없다.
알고리즘은 역시 말로 설명할 수 없다. 그림 설명이 최고다.