문제https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.www.acmicpc.net 설명각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구해야 한다.이번 문제에서는 크루스칼 알고리즘을 통해 최소 신장 트리를 구할 것이다.먼저 간선의 정보를 저장할 Edge 클래스를 만든다.우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다.static class Edge implements Comparable { int current; int dest; int cost; ..
문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 설명 (n + 1) 개의 집합 { 0 }, { 1 }, { 2 }, ... , { n } 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 각 (n + 1) 개의 집합은 서로소 집합이다. 합집합 연산이 필요할 때에는 union()를 사용하고 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산이..
서로소 집합 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 - Union 연산 어떤 두 원소 a, b 에 대해서, union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산이다. \(a \in A, b \in B\) 에 대해서, union(a, b)는 \(A \cup B\) 이다. - Find 연산 어떤 원소 a에 대해서, find(a)는 a가 속한 집합(집합의 대표번호)을 반환하는 연산이다. \(a \in A\) 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환한다. 서로소 집합의 표현 - 초기화 - Union 연산 ex) union(1, 2) - Find 연산 ex) find(3) = 1, find(5) = 1 서로소 ..
