NineTwo meet you

프림 (Prim) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 방식 동작 과정 1. 그래프를 확인하고 출발 노드를 우선순위 큐에 저장한다. (start, 0) 이때 저장되는 가중치는 자기 자신이므로 0이다. 우선순위 큐 : (0, 0) 2. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 : (2, 1), (1, 5) 3. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 ..

크루스칼 (Kruskal) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘 간선을 오름차순으로 정렬하고 이미 트리에 추가된 간선과 사이클을 이루지 않을 때 간선을 추가 간선이 사이클이 되지 않는지 확인하기 위해 유니온 파인드를 사용 동작 과정 1. 가중치가 오름차순으로 정렬된 우선순위 큐에 모든 간선을 추가한다. 우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치) : (0,1,1), (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5) 2. poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)..