스패닝 트리??? 알고리즘을 공부하면서 스패닝 트리라는 단어를 처음 들어본 것 같다. 그래서 조금 더 알아봐야 겠다는 생각을 하게 됬다.
스패닝트리는 모든 정점을 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 이 부분에서 [ 사이클이 존재하지 않는다 ] 는게 중요 포인트인 것 같다.
그래서 [ 출발 지점 ] 에서 [ 도착 지점 ] 까지 도착하는데, 최소한의 거리로 가는 방법을 찾는 문제를 최소 스패닝 트리라고 할 수 있다고 한다.
코딩 테스트를 칠 때 많이 나오는 문제이기도 하고, DFS나 BFS로 풀면 된다고는 알고 있었지만, 이를 풀기 위해 많은 알로리즘 법칙이 있다는 것을 알게 되었다.
문제를 계속해서 조금 더 많이 풀어보고, 문제 유형을 많이 익혀야 앞으로 문제 해결할 때 어떤 알고리즘을 쓸지 감을 익힐 수 있을 것 같다.
초보개발자