Dev.baelanche

유니온파인드 문제이다. 정답률이 높아서 쉬운줄 알았는데 꽤나 애먹었다. 아래와 같은 방법으로 풀었다. 1. 친구관계를 기록할 배열, 친구비용 배열, 친구번호와 비용을 모두 가진 클래스 배열을 만든다. 2. 친구관계가 주어지면 union 연산을 한다. 3. 클래스 배열의 루트 인덱스에 친구 비용의 최솟값을 저장한다. 4. k가 최솟값의 총합보다 같거나 크면 비용을 출력한다. public class Main { static int a[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; ..

유니온파인드 문제이다. 두 도시의 연결정보가 주어지면 union 연산을 한다. 여행계획이 주어졌을때 매 도시마다 find 연산을 하여 루트가 모두 같으면 YES 하나라도 다르면 NO를 출력한다. public class Main { static int a[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); a = new int[n]; Ar..

처음 풀어보는 유니온파인드 문제이다. 후에 되새기는 용으로 간단히 서술해보겠다. 유니온파인드(Union-Find)는 자료구조의 이름으로 disjoint-set(서로소 집합)이라고도 부른다. 1개 혹은 그 이상의 집합들은 서로 교집합이 없고 그 집합들의 합집합은 전체집합과 같다. 이 자료구조는 Union 연산(합연산)과 Find 연산(루트 검색)만이 있다. 문제 풀이 및 유니온파인드 구현을 같이 했다. public class Main { int tree[]; int size; Main(int size) { tree = new int[size+1]; this.size = size; Arrays.fill(tree, -1); } void set(int root, int child) { tree[child] = ..