"방문 안 한 정점 중 최단 거리를 지닌 정점을 찾기"를 배열 내에서 선형탐색하면 O(n)이고, 우선순위큐를 쓰면 o(logn)이잖아?
방문한 정점은 오른쪽 정점을 가리키고, 방문안한 정점은 자기 자신을 가리키도록 유니온파인드를 쓰면 시간복잡도가 더 빨라지지 않을까. 루트가 방문 안 한 정점이 되게끔.
경로 압축 이미 된거 기준으로 사진에서는 find(0)으로 인덱스 3, find(4)로 인덱스 5, find(6)로 인덱스 dummy를 가리킴. 총 3번만 탐색하면 돼서 선형탐색 7번보다 적게 필요함
O(v*find시간 + e*union시간)으로 빨라질 거 같음. 키햐 지렸다 생각이 들다가도 내가 이런 발상을 한 첫 사람은 아닐 거란 생각이 들더라. 근데 구글에 찾아보니 딱히 없더라고.
문제점 혹은 전례가 뭐가 있을까
총 3번만 탐색하면 돼서 선형탐색 7번보다 적게 필요함 -> 우선순위 큐 쓴 logn보다 느린거 아님?
그건야 그런데 그냥 호기심이지
내가 이해를 잘못한 건진 몰라도 유파 시간 제외해도 똑같이 N^2아님? 어차피 방문하지 않은 정점만 돈다고 해도 최소값이 어디 있는지를 모르니 방문하지 않은 정점을 다 탐색해야 하잖아... N N ... N번 탐색하는 걸 N N-1 ... 1로 바꾸는 거로 보여요
아 맞네. 그러네. N/2가 될 뿐이네. 7번 대신 3번이라고 적어놓고 왜 그냥 1로 간주한 거지 난.
다익은 아닌데 배열의 현재 원소의 왼쪽과 오른쪽이 바뀔 때 얘의 왼쪽/오른쪽을 유파로 연결하는 걸 보긴 함