[프로그래머스] (Java) 유니온 파인드 구현하기

 

 

📑 1. 문제설명

간단한 유니온 파인드 알고리즘 구현하기

• union(x, y) : x와 y가 속한 두 집합을 합칩니다.
• find(x) : x가 속한 집합의 대표 원소를 찾습니다.

operations 라는 배열은 수행할 연산을 의미한다. 연산 종류는 2개이다.

• [0, 1, 2]는 노드1과 노드2에 대해  union 연산 수행
• [1, 1, 3] 노드 1과 3이 같은 집합에 속해 있으면 true, 아니면 false를 반환하는 equals 연산

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정하며 여기서는 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법을 사용한다. operations에 있는 연산에 대한 결과를 연산 순서대로 담은 Boolean 배열을 반환하는 solution() 메서드를 구현하기

 

제약조건

• 0 <= k <= 1,000 : 노드의 개수
• 1 <= len(operations) <= 100,000
• operations[i][0]은 문자열 'u' 또는 'f' 중 하나
• 0은 union 연산, union 연산 뒤로는 두 개의 정수 x,y가 나옴
• 1은 equals 연산, equals 연산 뒤로는 두 개의 정수 x,y가 나옴
• x와 y는 0 이상 k-1 이하의 정수
• 연산은 항상 유효함
  • 즉, union, find 연산의 인수는 상호배타적 집합 내에 있는 노드 번호

입출력의 예

k	operations	result
3	[[0, 0, 1], [0, 1, 2], [1, 1, 2]]	[true]
4	[[0, 0, 1], [1, 1, 2], [0, 1, 2], [1, 0, 2]]	[false, true]

---

💡 2. 풀이과정

아주 쉽게 말해서 초등학생의 눈높이로 말하면 '친구 그룹 만들기'라고 생각하면 된다. 

• 친구들이 있다. 예를 들어, 0, 1, 2 라는 친구가 있다.
• 우리가 친구들을 손 잡기 시키면서 누가 누구랑 같은 그룹인지 확인하려고 한다.
• 이미 손을 잡고 있는 친구끼리는 또 잡으면 안 된다. 

만약 아래와 같은 예시가 있다고 하자, 요소의 첫번째가 0이면 union이고, 1이면 find를 수행한다. 

[[0,0,1],[0,1,2],[1,1,2]]

• 첫번째는 [0, 0, 1]
  → 친구 0과 1을 연결하는 것이다.
• 두 번째는 [0, 1, 2]
  → 친구 1과 2를 연결하는 것이다. 이 때 1은 이미 0이랑 연결되어 있기 때문에
  → 이제 0, 1, 2 모두 같은 그룹이다.
• 세 번째는 [1, 1, 2]
  → 앞에 1이 오기 때문에 1과 2가 같은 그룹인지 확인한다. 같은 그룹이므로 true를 리턴한다. 

 

친구끼리 연결 → Union (합치기)
이미 연결된 친구끼리는 또 연결 불가 → Find (찾기)
연결 성공 여부를 true/false로 기록

 

 

[true/false] 체크는 “앞에 있는 숫자가 이미 연결돼 있는 그룹에 포함돼 있는지”를 보는 것이다. 

 

parent배열, union 메서드, find 메서드, 그리고 결과값을 담아줄 boolean[] answer배열이 필요하다.

 

parent 배열이 하는 일은 각 노드가 속한 집합의 대표 루트 노드 번호를 저장하는 것이다. 문제에서 초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정했기 때문에 여기서는 먼저 노드의 수 길이  parent를 선언하고, 각자 자기 자신을 부모로 가지는 것으로 초기화한다. 

 

union 메서드는 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법을 사용한다. 여기서 문제 오류가 있는 것 같은데, 작은 노드를 큰 노드의 자식으로 연결한다는 조건이 있으나 보통은 그 반대이다. 보통 최적화 할때 작은 루트를 루트로 하고, 큰 루트를 그 아래 자식으로 붙인다. 왜냐하면 트리 높이를 낮추기 위해서이다. 아래와 같이 구현한다.

if (rootX < rootY) {
    parent[rootY] = rootX; // rootY(큰 루트)를 rootX(작은 루트) 아래로
} else {
    parent[rootX] = rootY; // rootX(큰 루트)를 rootY(작은 루트) 아래로
}

 

find 메서드는 유니온파인드에서 x가 속한 집합의 루트 노드(대표)를 찾는 메서드이다. x가 속한 집합이 어느 집합인지 확인할 때 사용한다. 현재 노트 x가 자기 자신을 루트로 가지고 있는지 확인하고

 

• parent[x] == x → 루트 노드
• parent[x] != x → 루트가 아님 → 부모를 따라 올라가야 함

재귀적으로 부모를 따라 올라가 루트를 찾으며 경로 압축을 해야 시간이 단축된다.

경로압축을 안 하면 아래처럼 된다.

private static int find(int x) {
    if (parent[x] == x) {
        return x; // 루트면 그대로 반환
    }
    return find(parent[x]); // 루트까지 재귀적으로 올라감
}

 

중간 노드들의 parent를 루트로 바로 안 바꾸면 트리 높이가 그대로 유지된다. 하지만 아래처럼 하면 x의 부모를 바로 루트로 바꾸기 때문에 한 번 find를 거치면, x와 그 위 노드들은 모두 루트를 바로 부모로 삼는다.

private static int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 경로 압축
    }
    return parent[x];
}

 

마지막으로 boolean[]을 리턴해야 하는데 ArrayList를 쓴 이유는 미리 리턴할 배열의 길이를 모르기 때문이다. 물론 operations 배열을 반복문으로 순회하면서 operation[i][0]의 값이 1인 것의 개수만 세어서 해도 되지만 그렇게 하면 시간이 더 오래 걸리기 때문에 결과 개수가 동적으로 늘어날 수 있는 ArrayList를 사용한 것이다.

---

👨‍💻 3. 정답코드

package unionFind;

import java.util.ArrayList;

public class unionFind {
	// 부모 저장을 위한 배열
	private static int[] parent;
	
	// find 메서드 
	private static int find(int x) {
		if (parent[x] != x) {
		    parent[x] = find(parent[x]);
		}
		return parent[x];
	}
	
    /*
	private static void union(int x, int y) {
		int root1 = find(x); // x가 속한 집합의 루트 노드 찾기
		int root2 = find(y); // y가 속한 집합의 루트 노드 찾기
		parent[root2] = root1; // y가 속한 집합을 x가 속한 집합에 합치기
	}
    */
    
    // union 메서드
    // 문제에서 루트 기준으로 작은 노드를 큰 노드의 자식으로 연결한다는 조건 추가
    // 문제 오류
    // 실제 구현에서 트리 높이를 낮추려면 작은 루트가 루트, 큰루트가 자식이 되어야 함
    private static void union(int x, int y) {
        int root1 = find(x); // x가 속한 집합의 루트 노드 찾기
        int root2 = find(y); // y가 속한 집합의 루트 노드 찾기
        if (rootX < rootY) {
            parent[rootY] = rootX; // 큰 루트가 작은 루트 아래로
        } else {
            parent[rooxX] = rootY; // 작은 루트가 큰 루트 아래로
        }
    }
    
	
	private static Boolean[] solution(int k, int[][] operation) {
		// 노드의 수 만큼 배열 생성
		parent = new int[k];
		// 처음에는 각 노드가 자기 자신을 부모로 가지도록ㄹ 초기화
		for (int i = 0; i < k; i++) {
			parent[i] = i;
		}
		
		ArrayList<Boolean> answer = new ArrayList<>();
		
		for (int[] op : operation) {
			if (op[0] == 0) { // 0 연산이면 union
				union(op[1], op[2]);				
			} else {
				answer.add(find(op[1]) == find(op[2]));
			}
		}
		return answer.toArray(new Boolean[0]);
	}
	
	
	public static void main(String[] args) {
		int k = 5;
	    int[][] operations = {
	        {0, 1, 2}, // union(1, 2)
	        {0, 2, 3}, // union(2, 3)
	        {1, 1, 3}, // find(1), find(3) → true
	        {1, 1, 4}  // find(1), find(4) → false
	    };
	    
	    Boolean[] result = solution(k, operations);
	    for (Boolean b : result) {
	    	System.out.println(b);
	    }
	}
}

 

중간에 UNION 메서드 구현 할 때 작은 루트를 루트로 하고, 큰 루트를 그 아래 자식으로 붙이는 처리를 하지 않아서 다시 작성했다. 이전 코드는 주석처리했다.