MST 썸네일형 리스트형 백준 15481 그래프와 MST 역시 LCA를 활용하는 문제이다. 저번 정점들의 거리 문제에서 MST의 개념을 살짝 붙이기만 하면 방법을 찾을 수 있다. 에지를 입력받을 때, 인접 행렬을 직접 만드는 것이 아니라, 에지만 저장하는 벡터/배열을 선언하고 나중에 그 에지들을 순회하며 MST를 찾을 수 있게 한다. std::vector adj[N]; std::priority_queue pq; std::vector vEdgeList; 일단 에지를 입력받고 난 다음, 그 에지들을 사용해 MST를 계산한다. MST를 계산하면서 adj(인접행렬)을 채워 이 트리를 사용해 LCA를 구하게 된다. for (int i = 0; i > s >> e >> c; s--; e--;.. 더보기 [나만 몰랐던 알고리즘] MST 구하기 - Kruskal's Algorithm Minimun Spanning Tree는 모든 노드를 잇는 사이클이 없는 그래프 중 간선(edge)의 가중치 합이 최소가 되는 트리(그래프)이다. 글로 봤을땐 저게 뭔가 싶은데 그림으로 한번 보자 위 사진과 같은 그래프에서, 모든 노드를 포함하는 부분 그래프를 신장 부분 그래프라고 한다. 여기서 간선이 어떻게 연결되는지에 따라 여러개의 신장 부분 그래프를 만들 수 있는데, 이 중 간선의 합이 최소가 되는 신장 부분 그래프를 MST라고 하고, 오늘 정리할 알고리즘은 이 MST를 찾는 Kruskal 알고리즘이다. 알고리즘을 크게 정리하면, 모든 에지를 Cost 순으로 정렬되는 Priority Queue에 넣는다. PQ에서 하나를 뽑는다 -> 이 에지의 출발점과 도착점이 연결되어 있지 않다면 트리에 추가한다... 더보기 이전 1 다음
