그래프 최소 스패닝 트리 문제 1 여행 경로 정하기

문제 파악

일반적인 최소 스패닝 트리는 트리의 가중치 합이 최소가 되어야 한다. 그러나 이 문제의 요구 조건은 스패닝 트리를 이루는 가중치의 최대값과 최소값의 차이가 최소가 되어야 하는 것이다.
생각한 방식은 min값과 max값을 계속 갱신해 나가면서 스패닝 트리를 만드는 것인데 이렇게 되면, 가중치를 정렬함으로써 간선을 효율적으로 선택할 수 있어서 얻어지는 크루스칼 알고리즘의 효율성이 떨어지게 된다.

문제 풀이

문제 풀이의 핵심 아이디어는 가중치의 하한을 정해두고 최소 스패닝 트리를 만드는 것이다. 간선을 선택할 때 그 간선의 가중치가 하한보다 작다면 그 간선은 선택되지 않는다. 또한 간선을 가중치가 작은 순서부터 선택하기 때문에 이 문제의 조건인 시작점과 끝점이 연결되는 순간 알고리즘을 종료시키고, 그 때의 가중치를 저장하면 그 가중치가 선택된 간선들의 가중치의 최대 값이 된다.

이 문제의 입력 조건을 살펴보면 이 문제는 E^2*logE의 시간 복잡도로는 문제의 시간 제한을 확실히 통과한다고 보기 어렵다. 크루스칼 알고리즘의 시간 복잡도는 ElogE인데 이 때 시간 복잡도를 결정하는 부분은 간선들을 가중치 순으로 정렬하는 부분이다. 따라서 가중치를 한 번만 정렬해 놓으면 크루스칼 알고리즘을 여러번 돌릴 때 다시 정렬할 필요가 없다. 이렇게 되면 크루스칼 알고리즘의 시간 복잡도는 E가 된다.

따라서 이 풀이의 시간 복잡도는 크루스칼 알고리즘을 동작하는데 E, 각 간선의 가중치 별로 동작시키는데 E가 되어 E^2이 된다.

느낀점

하한 또는 상한을 설정해 줌으로써 문제를 단순화 시킬 수 있다. 반복해서 같은 값이 계산되면 반복문 바깥으로 빼주는게 효율적이다.