728x90 크루스칼 알고리즘3 [C++] 크루스칼 알고리즘(Kruskal Algorithm, 최소 스패닝 트리-MST) 개념 크루스칼 알고리즘이란? 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 이는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 대표적으로 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘입니다.(크루스칼 알고리즘을 구현할 때 기본적으로 유니온 파인드 개념을 사용합니다.) 예시코드 class edge { public: int node[2]; int distance; edge(int a, int b, int c) { this->node[0] = a; this->node[1] = b; this->distance = c; } bool operator distance .. 2021. 8. 23. [C++] 백준 4386번: 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 유니온-파인 알고리즘의 개념과 이미 연결되어 있는 그래프를 파악하여 그래프에 사이클이 존재하는지 여부를 지속적으로 확인하여 줍니다. 이러한 기법을 크루스칼 알고리즘 또는 최소 스패닝 트리라고 합니다. #include #include #include #include using namespace std; class edge { public: int node[2]; float distance; ed.. 2021. 8. 19. [C++] 백준 1774번: 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 풀이 우선 최소 스패닝 트리 알고리즘이 사용되었고 이는 유니온-파인 알고리즘에 바탕을 둡니다. 다른 점으로는 클라스를 통해 트리 형태를 구현해 줍니다. 이와 함께 최소 스패닝 트리 구현을 진행해 줍니다. #include #include #include #include using namespace std; class edge { public: int node[2]; dou.. 2021. 8. 19. 이전 1 다음 728x90
