[백준] 24391번 '귀찮은 해강이' - Java

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 51140KB | 시간 464ms | 코드 길이 1485B

import java.io.*;
import java.util.*;

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int[] parent;
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		parent = new int[n];
		
		for(int i = 0 ; i < n ; i++) {
			parent[i] = i;
		}
		
		for(int i = 0 ; i < m ; i++) {
			StringTokenizer st_node = new StringTokenizer(bf.readLine());
			int x = Integer.parseInt(st_node.nextToken()) - 1;
			int y = Integer.parseInt(st_node.nextToken()) - 1;
			union_root(x, y);
		}
		
		StringTokenizer st_order = new StringTokenizer(bf.readLine());
		int[] order = new int[n];
		for(int i = 0 ; i < n ; i++) {
			order[i] = Integer.parseInt(st_order.nextToken()) - 1;
		}
		
		int cnt = 0;
		for(int i = 0 ; i < n-1 ; i++) {
			if(find_root(order[i]) != find_root(order[i + 1])) {
				cnt ++;
			}
		}
		
		bw.write(Integer.toString(cnt));
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	private static int find_root(int x) {
		if(x == parent[x]) {
			return x;
		}
		return parent[x] = find_root(parent[x]);
	}
	
	private static void union_root(int x, int y) {
		x = find_root(x);
		y = find_root(y);
		
		if(x != y) {
			parent[x] = y;
		}
	}
}

분리 집합을 이용한 풀이입니다.

parent 배열에는 각 인덱스(노드)에 대한 루트노드를 넣습니다.

find_root에서는 매개변수로 들어올 값의 루트노드를 리턴합니다.

union_root에서는 매개변수로 두 값을 받아서 두 노드를 병합해줍니다.

 

find_root 로는 루트노드를 알게 되고, 이를 이용하여 union_root로 두 노드를 병합한다고 보시면 됩니다.

https://4legs-study.tistory.com/94

분리 집합 (Disjoint Set) : Union-Find

위 링크에 설명이 잘 되어있습니다.