union-find3 [Problem Solving] BOJ 10775 : 공항 문제 링크 : https://www.acmicpc.net/problem/10775 P대의 비행기가 순서대로 공항에 들어오게 되는데, i번째 비행기는 1번부터 G[i]번 게이트중 하나에 도킹하려고 할 때, 비행기가 어느 게이트에도 도킹할 수 없다면 이후 어떤 비행기도 공항에 도착할 수 없다. 이 때 공항에 도착할 수 있는 비행기의 최대 수를 구하는 문제이다. 이 문제는 Union-Find로 해결할 수 있다.G = 4일 때 parent 배열은 다음과 같다.parent = [0, 1, 2, 3, 4]i번째 요소의 값은 비행기가 1번부터 i번의 게이트에 도킹하려고 할 때, 비행기가 도킹할 수 있는 게이트 번호의 최댓값이다. find 결과의 값이 0이 나온다면 비행기가 어느 게이트에도 도킹할 수 없는 것이다. 6.. 2025. 2. 6. [Computer Algorithms] Kruskal's Algorithm (크러스컬의 알고리즘, 최소신장트리) 1. {{노드 x, 노드 y}, 노드 사이 간선의 가중치 w} 를 배열에 저장하고, w를 기준으로 오름차순 정렬한다.2. w가 작은 간선 부터 간선에 연결되어 있는 노드들의 disjoint-set을 구한다.3. 사이클이 존재하지 않는 최소 신장 트리(트리이기 때문에 사이클이 존재하지 않는 것은 당연하다.)의 간선의 합을 구할 수 있다.#include #include #include using namespace std;int V, E;int parent[101];int result = 0;vector, int>> edges;bool compare(const pair, int> &a, const pair, int> &b){ return a.second > V >> E; for (int i = 1;.. 2024. 6. 28. [Computer Algorithms] Disjoint-Set : Union-Find (서로소 집합) 1. 각 노드의 부모를 자기 자신으로 초기 설정한다.2. Find는 한 set에 있는 노드들의 부모 노드로의 경로를 압축하여 노드들이 공통된 하나의 부모 노드를 가리키게 하고, 이를 return하게 한다.3. Union는 두 노드의 부모 노드를 비교하여 큰 수의 부모 노드가 작은 수의 부모 노드의 자식 노드가 되게 한다. #include #include #include using namespace std;int V, E;int parent[101];int find_parent(int x){ if (parent[x] != x) parent[x] = find_parent(parent[x]); return parent[x];}void union_parent(int x, int y){ .. 2024. 6. 28. 이전 1 다음