그러한 기준이 없다면 루트노드로 수렴하지 않을 것 같습니다.
크루스칼에서 왜 꼭 작은 부모노드를 기준으로 이동해야 하는지 모르겠습니다.
1197번 - 최소 스패닝 트리
아무렇게나 노드를 합친다면 운이 나쁜 경우 줄줄이 1자로 노드가 연결될 수 있습니다.
이렇게 되면 자식으로부터 부모를 찾는 ancestor() 함수의 동작 시간이 O(V) 만큼 길어져서 느려집니다. 작은 노드를 기준으로 하면 이런 일이 안생깁니다.
작은 노드를 기준으로 합치는 건, 그저 일관된 merge 기준을 잡은 것에 불과 합니다.
가장 보편적이기도 하구요.
19행에서 '>'가 '<'로 되어도 전혀 문제가 없죠.
일관된 merge에 따라 약간의 경로 압축이 이루어졌기 때문에 시간 초과 유무가 갈리는 것입니다.
하지만 지금 코드 역시 완전한 경로 압축이 이뤄지지 않았어요.
경로 압축을 제대로 하기 위해선 ancestor(node) 내부에서 루트 노드를 찾아가는 과정에서도 위 기준이 적용 되어야 합니다.
즉 궁극적인 목적은 다음의 상황을 생각해 봅시다.
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
크루스칼 진행 도중 위와 같이 사향 트리의 모양이 만들어져있고, 아직 확인하지 않은 간선들은 9와 e개 연결되어 있다고 해 봅시다.
그럼 e개의 간선을 돌아볼 때마다 ancestor(9)에서 위 모양을 따라 계속 비효율적인 동작을 하겠죠.
하지만 위처럼 단순히 9개가 아닌 10만 개의 노드가 저 모양으로 연결된 상황이라면 어떻게 될까요 ?
이런 불상사를 막기 위해 ancestor(node) 과정에서도 계속 노드들의 parent값을 갱신해 주는 것입니다.
그럼 결국 일자 모양의 사향 트리가 마치 선인장처럼 루트 노드를 중심으로 이 집합에 속한 노드들이 둘러싼 형태가 되겠죠.
'경로 압축'이란 것에 대해 공부해 보세요.
댓글을 작성하려면 로그인해야 합니다.
dlrjs2360 3년 전
안녕하세요.
크루스칼 알고리즘에 대해서 궁금한 점이 있어서 질문글 남깁니다.
제가 생각하는 크루스칼 알고리즘은
" 가중치가 낮은 순서로 간선들을 뽑아서 그래프를 형성하고 그래프끼리 만나면 부모노드를 통일시켜서 그래프를 합쳐준다 " 입니다.
근데 다른 코드들이나 블로그들을 보게 되면 항상 부모노드들 중에서 작은 노드를 기준으로 통일하라고 합니다.
사실 저는 이 부분이 왜 그러한지 이해하지 못하였고 예전에 크루스칼 알고리즘을 해결할 때 작은 노드를 기준으로 하지 않고도 통과하였습니다.
그런데 이번 문제에서 작은 노드를 기준으로 통합하지 않으면 시간초과가 나서 정답처리가 되지 않았습니다.
작은 노드를 기준으로 부모노드를 통일해야 하는지 그 이유를 잘 모르겠습니다.
스피드웨건 부탁해요~~