[백준] 집합의 표현(유니온 파인드 알고리즘)

백준 온라인 저지 1717번 - 집합의 표현

지난 유니온 파인드 알고리즘 포스팅에서 공부한 것을 적용하기 위해 유니온 파인드 알고리즘을 활용한 문제를 풀이했다.
문제 조건에 맞게 type 1인 연산일 경우 a와
b가 같은 집합에 포함되어 있는지를 확인하는 checkSame() 메소드를 추가로 만들어 주었고 포스팅에서 공부한 것 처럼 find() 메소드에서 else 조건일 때 parents[t]에 find(parents[t])의 리턴값을 업데이트 해 줌으로써 시간복잡도를 줄여주어 알고리즘의 성능을 향상시키도록 했다.

SetExpression.java

package com.example.Baekjoon;

import java.util.ArrayList;
import java.util.List;

/**
 * 집합의 표현
 * 유니온 파인드 알고리즘으로 풀이
 */
public class SetExpression {

    static int[] parents;

    public List<String> doExpression(int n, int m, List<Operation> operations) {

        List<String> answer = new ArrayList<>();

        // 1. 대표 노드 초기화
        parents = new int[n + 1];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }

        // 2. 연산 처리(계산)
        for (Operation op : operations) {
            if (op.type == 0) { // 유니온 연산
                union(op.a, op.b);
            } else { // 두 원소 값 동일 체크
                answer.add(checkSame(op.a, op.b));
            }
        }

        return answer;
    }

    private void union(int a, int b) {
        int findA = find(a);
        int findB = find(b);
        if (findA != findB) {
            parents[b] = findA; // 두 개 그래프 연결
        }
    }

    private int find(int t) {
        if (parents[t] == t) {
            return t;
        } else {
            // value를 index로 변경해서 또 find 연산, parents[t]에 넣는 이유는 경로 압축을 위함
            return parents[t] = find(parents[t]);
        }
    }

    private String checkSame(int a, int b) {
        int findA = find(a);
        int findB = find(b);

        if (findA == findB) {
            return "YES";
        } else {
            return "NO";
        }
    }
}

class Operation {

    int type;

    int a;

    int b;

    public Operation(int type, int a, int b) {
        this.type = type;
        this.a = a;
        this.b = b;
    }

}

SetExpressionTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class SetExpressionTest {
    @Test
    public void testSetExpression() {

        SetExpression se = new SetExpression();

        List<Operation> operations = Arrays.asList(
                new Operation(0, 1, 3),
                new Operation(1, 1, 7),
                new Operation(0, 7, 6),
                new Operation(1, 7, 1),
                new Operation(0, 3, 7),
                new Operation(0, 4, 2),
                new Operation(0, 1, 1),
                new Operation(1, 1, 1));

        String[] result1 = se.doExpression(7, 8, operations).stream().toArray(String[]::new);

        String[] expected = new String[] { "NO", "NO", "YES" };

        assertArrayEquals(expected, result1);
    }
}