목록유니온 파인드 (19)

1일1알

백준 21924번 도시 건설 C++

유니온 파인드를 이용해서 최소 스패닝 트리를 만들었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; struct Info { int a; int b; int cost; bool operator height[v]) ::swap(u, v); parent[u] = parent[v]; if (height[u] == height[v]) height[v]++; } int main() { ios_base::s..
알고리즘 2022. 8. 5. 12:43
백준 3197번 백조의 호수 C++

매번 빙판이 녹는것과 백조가 만날 수 있는지를 bfs를 돌리면 시간초과가 난다. 그렇기 때문에 각 구역마다 번호를 지정해두고 유니온 파인드를 이용해 빙판이 녹아서 합쳐지면 두 구역을 합쳐주면서 백조가 같은 구역에 있는지를 검사하면 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int r, c; int head = 0; vector found; vector board; vector parent; vector h..
알고리즘 2022. 7. 25. 13:07
백준 16724번 피리 부는 사나이 C++

유니온 파인드를 이용해서 몇개의 집합으로 나누어져 있는지 구했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; vector parent; vector height; vector board; pair Index2RowCol(int idx) { int row = idx / m; int col = idx..
알고리즘 2022. 7. 22. 11:58
백준 20040번 사이클 게임 C++

유니온 파인드를 이용해서 두 점이 이미 같은 집합이라면 두 점을 이었을 때 사이클이 생긴다는 것을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; vector parent; vector height; int GetParent(int n) { if (n == parent[n]) return n; return parent[n] = GetParent(parent[n]); } void Merge(int u,..
알고리즘 2022. 7. 12. 12:38
백준 4386번 별자리 만들기 C++

모든 별끼리 서로 연결될 수 있기 때문에 이어질수 있는 모든 경로를 후보로 두고 거리가 작은 순서로 정렬한 뒤 최소 스패닝 트리를 이용하여 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; struct Pos { int head; double x; double y; }; struct LoadInfo { Pos start; Pos end; double dist; bool operator height[..
알고리즘 2022. 7. 10. 14:32
백준 1647번 도시 분할 계획 C++

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리를 구하고 최소 스패닝 트리로 연결된 길 중에서 유지비의 값이 가장 높은 길을 빼면 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; struct LoadInfo { int start; int end; int cost; bool operator height[v]) ::swap(u, v); parent[u] = v; if (height[u] == ..
알고리즘 2022. 7. 9. 14:59
이전 Prev 1 2 3 4 Next 다음