본문 바로가기
728x90

🥇Baekjoon Solutions/Union-Find & 크루스칼 알고리즘11

[C++] 백준 1647번: 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 조건 마을 간 도로 유지비용을 최소로 N:집의 개수, M:길의 개수 N(2~100,000), M(1~1,000,000) A B C -> A,B집을 연결하는 길의 유지비 C(1~1,000) *최소 스패닝 트리를 구하고 가장 큰 연결선 제거 #include #include #include using namespace std; int N, M; int road[10.. 2021. 9. 25.
[C++] 백준 20040번: 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 중요풀이 union-find 알고리즘을 활용하여 풀이를 진행한 대표적인 문제입니다. union-find 알고리즘을 적용한다면 무난하게 풀어지는 문제입니다. 소스코드 #include using namespace std; int parent[500001]; int find(int index) { if (parent[index] == index)return index; return parent[i.. 2021. 8. 23.
[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++] Union-Find 알고리즘 개념 Union-Find 알고리즘이란? 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가진 알고리즘입니다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부릅니다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 선택된 두 노드가 서로 같은 그래프 상에 속해 있는지 판별하는 알고리즘입니다. 구현된 함수로는 조상 노드를 찾는 getParent(재귀함수로 구현)함수와 합집합해주는 unionParent함수 그리고 두 노드가 같은 그래프에 있는지 확인해주는 findParent함수가 있습니다. //보통 union find 알고리즘을 사용할 때 갱신을 작은 수쪽으로 수정해줍니다. //parent 찾기 int getParent(int parent[], int x) { if (parent[x] == .. 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++] 백준 4195번: 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온-파인 알고리즘과 해쉬맵을 활용하여 풀이를 진행하였습니다. 해쉬맵은 인덱스가 많을 시 효율성이 떨어지지만 이렇게 자료가 한정적인 문제에서는 사용에 유리합니다. #include #include #include using namespace std; int N, M, parent[200001], cnt[200001]; map m; int find(int index) { if (pa.. 2021. 8. 19.
[C++] 백준 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 그래프 탐색 기법을 이용하여 풀이를 진행하였습니다. 활용된 알고리즘으로는 유니온-파인 알고리즘을 활용하여 그래프들의 연결 상태를 파악하며 그래프 탐색을 진행합니다. #include using namespace std; int city[201]; int node[1001]; //보통 union find 알고리즘을 사용할 때 갱신을 작은 수쪽으로 수정해줍니다. //parent 찾기 int get.. 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.
[C++] 백준 1717번: 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 유니온-파인 알고리즘의 기본문제로 배열을 정의하고 앞서 배운 유니온 파인 알고리즘의 함수를 가지고 풀이를 진행하였습니다. #include using namespace std; int parent[1000001]; //parent 찾기 int getParent(int parent[], int x) { if (parent[x] == x)return x; .. 2021. 8. 19.
728x90

티스토리툴바