유니온 파인드 자바 백준 BOJ 1717, 1976, 1043

 

유니온 파인드 union-find 는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해서 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘입니다.

 

union 연산

각 노드가 속한 집합을 1개로 합치는 연산입니다.

노드 a, b 가 a ∈ A, b ∈ B 이 때 union(a,b) 는 A ∪ B 을 뜻합니다.

find 연산

특정 노드 a 에 관해 a 가 속한 집합의 대표 노드를 반환하는 연산입니다. 

노드 a 가  a ∈ A 일 때 find(a) 는 A 집합의 대표 노드를 반환합니다.

 

 

유니온 파인드 알고리즘 구현 방법

유니온 파인드 알고리즘 구현 방법을 아래 예를 통해서 알아봅시다.

 

1. 유니온 파인드는 일반적으로 1차원 배열을 이용해서 표현합니다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됩니다. 각 노드가 모두 대표 노드이므로 자신의 인덱스값으로 초기화합니다.

2. 2개의 노드를 선택해서 각각의 대표 노드를 찾아서 연결하는 union 연산을 수행합니다. 1, 4 그리고 5, 6 을 union 연산으로 연결한다면 배열[4] = 1, 배열 [6] =5 로 업데이트합니다. 

1은 대표노드, 4는 그에 대해서 자식 노드가 되어 각각의 집합이었던 1, 4 는 하나로 합쳐진 것입니다. 5, 6의 경우도 그렇습니다.

 

 

3. 이 상태에서 union(4, 6) 연산을 해봅시다. 이 때 4, 6 은 대표노드가 아닙니다. 그래서 각 노드의 대표 노드를 찾아 올라간 다음에 그 대표노드를 연결합니다. 그 결과 4의 대표노드 1과 6의 대표노드 5가 연결됩니다. 

 

find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산압니다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 감소시킵니다. 

 

find 연산의 작동 원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인.

2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동.

3. 이동 위치의 index 값과 value 값이 같을 때까지 1 ~ 2 을 반복. (이 부분은 재귀 함수로 구현)

4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경.

 

 

find 연산은 연산을 할 때 겇치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되는 것을 알 수 있습니다. 이렇게 되면 추후에 노드와 관련된 find 연산 속도가 O(1) 로 변경됩니다.

 

한 번의 find 연산을 이용해서 모든 노드가 루트 노드에 직접 연결되는 형태로 변경됩니다. 경로 압축 의 효과가 나타나는 것이지요. 

경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말합니다.

 

백준 1717 집합의 표현

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

 

1. 문제 분석

최대 원소의 개수는 1,000,000 이고 최대 질의 개수가 100,000 으로 큰 편이므로 경로 압축이 필요한 전형적인 유니온 파인드 문제입니다. 

2. 손으로 풀기

1. 처음에는 노드가 연결되어 있지 않습니다. 각 노드의 대표 노드는 자기 자신입니다.

2. find 연산으로 특정 노드의 대표 노드를 찾고 union 연산으로 2 개의 노드를 이용해서 대표 노드를 찾아 연결합니다.

그리고 질의한 값에 따라 결과를 반환합니다.

 

3. 슈도코드

N: 원소 개수, M: 질의 개수
parent: 대표 노드 저장 배열
for(N){ 대표 노드를 자기 자신으로 초기화 }
for(M) {
    if(0 이면) 집합 합치기 -> union 연산
    else ->  같은 집합 원소인지 확인하고 결과값 출력
}

// union 연산
union(a, b){
    // a, b 의 대표 노드 찾기
    a = find(a); b = find(b);
    두 원소의 대표 노드끼리 연결하기
}

// find 연산
find(a){
    a 가 대표 노드이면 리턴
    아니면 a 의 대표 노드값을 find(parent[a]) 값으로 저장 -> 재귀함수 형태
}

// checkSame: 두 원소가 같은 집합인지 확인
checkSame(a,b){
    // a 와 b 의 대표 노드 찾기
    a = find(a); b = find(b);
    두 대표 노드가 같으면 true
    아니면 false
}

4. 코드

public class BaekJun1717Self {
    public static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        parent = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int query = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (query == 0) {
                union(a, b);
            } else {
                if (checkSame(a, b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    static int find(int node) {
        if (node == parent[node]) {
            return node;
        } else {
            return parent[node] = find(parent[node]);
        }
    }

    static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);
        return a == b;
    }

}

 

 

 

백준 1976 여행 가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

1. 문제 분석

도시의 연결 유무를 유니온 파인드 연산을 이용해서 해결할 수 있다는 아이디어만 떠올리면 쉽게 해결할 수 있습니다. 

일반적으로 유니온 파인드는 그래프 영역에서 많이 활용되지만 위처럼 단독으로도 활용할 수 있습니다.

도시 간 연결 데이터를 인접행렬에 저장 후, 인접 행렬을 탐색하면서 연결될 때마다 union 연산을 수행한은 방식으로 문제에 접근합시다.

2. 손으로 풀기

1. 도시와 여행 경로 데이터를 저장하고 각 노드와 관련된 대표 노드 배열의 값을 초기화합니다.

2. 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결되어 있을 때 union 연산을 수행합니다. 이 때 항상 큰 도시가 대표가 되도록 union 연산의 매개변수를 변경합니다.

3. 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 결과값을 출력합니다.

이 때 union, find 함수 구현은 위 문제와 동일합니다.

 

3. 슈도코드

N: 도시 수, M: 여행 계획에 속한 도시 수
parent: 각 도시의 대표 노드를 저장할 배열
city: 인접 행렬 형태로 그래프 표현
route: 여행 계획 순서에 맞게 저장한 도시 배열

for(N){
    for(N){ city 초기화 }
}
for(N) { parent 배열 초기화. 값 = 인덱스 }
for(M) { route 에 여행 도시 경로 저장 }

for(N) {
    for(N) {만약 인접 행렬에서 도시가 연결되어 있다고 하면 union 연산}
}

startParent = parent[route[0]]
for(M){
    만약 route 의 부모가 startParent 와 다르면
    isNO
}

isNO 이면 -> NO 출력
아니면 YES 출력

 

4. 코드

public class BaekJun1976 {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        parent = new int[N + 1];
        int[][] city = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        int[] route = new int[M];
        for (int i = 0; i < M; i++) {
            route[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (city[i][j] > 0) {
                    union(i, j);
                }
            }
        }

        int startParent = parent[route[0]];
        boolean isNO = false;

        for (int i = 1; i < M; i++) {
            int cur = find(route[i]);
            if (cur != startParent) {
                isNO = true;
                break;
            }
        }

        if (isNO) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    static int find(int node) {
        if (node == parent[node]) {
            return node;
        } else {
            return parent[node] = find(parent[node]);
        }
    }

}

 

 

백준 1943 거짓말

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

1. 문제 분석

이 문제의 핵심은 파티에 참석한 사람들을 하나의 집합이라고 생각하고 각각의 파티마다 union 연산을 이용해서 사람들을 연결하는 것입니다. 이 작업을 하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 됩니다. 

이후 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해서 확인함으로써 과장된 이야기를 할 수 있는지 판단할 수 있습니다.

 

2. 손으로 풀기

예제 입력 6을 이용해서 문제를 풀어봅시다. 

 

1. 대표 노드 자료 구조를 초기화합니다.

2. union 연산을 수행해서 각 파티에 참여한 사람들을 1개의 그룹으로 만듭니다.

3. find 연산을 수행해서 각 파티의 대표 토드와 진실을 아는 사람들이 같은 그룹에 있는지 확인합니다. 

같은 파티 사람 노드는 모두 연결되어 있으므로 아무 사람이나 지정해서 find 연산을 수행하면 됩니다.

 

4. 모든 파티에 관해서 과정 3을 반복하여 수행하고, 모든 파티의 대표 노드가 진실을 아는 사람들과 다른 그룹에 있다면 결과값을 증가시킵니다.

 

1번째 파티 (3, 4) -> find(3) = 3. (1, 2, 7) 에 속하지 않으므로 과장할 수 있음.

2번째 파티 (5) -> find(5) = 5. (1, 2, 7) 에 속하지 않으므로 과장할 수 있음.

3번째 파티 (5, 6) -> find(5) = 5. (1, 2, 7) 에 속하지 않으므로 과장할 수 있음.

4번째 파티 (6, 8) -> find(6) = 5. (1, 2, 7) 에 속하지 않으므로 과장할 수 있음.

5번째 파티 (8) -> find(8) = 5. (1, 2, 7) 에 속하지 않으므로 과장할 수 있음.

(만약 파티에서 임의로 지정한 사람의 대표 노드값이 1 또는 2 또는 7 이라면 과장할 수 없음.)

 

5. 과장할 수 있는 파티의 개수를 출력.

 

 

3. 슈도코드

N: 사람 수, M: 파티 개수
T: 진실을 아는 사람 수, trueP: 진실을 아는 사람 데이터, party: 파티 데이터
parent: 대표 노드 저장 배열

데이터를 입력받아서 각 자료구조에 저장하기
for(N) { 대표 노드를 자기 자신으로 초기화 }
for(i ~ M 만큼) {
    firstPerson: i 번째 파티의 첫번째 사람
    for(j ~ i 번째 파티의 사람 수만큼){
        // 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
        union(firstPerson, j)
    }
}
for(i ~ M 만큼){
    firstPeople: i 번재 파티의 첫번째 사람
    for(j ~ 진실을 아는 사람들의 수만큼){
        // 각 파티의 대표 노드가 진실을 아는 사람들의 대표 노드와 같다면 과장할 수 없음.
        find(firstPerson) 과 find(trueP[j]) 를 비교
    }
    위 반복문에서 모두 다르면 결과값을 1 증가
}
결과값 출력

// union - find 메서드
union(int a, int b){
    a 와 b 의 대표 노드 찾기
    두 원소의 대표 노드끼리 연결
}

find(int a){
    a 가 대표 노드라면 리턴
    아니라면 a 의 대표 노드값을 find(parent[a]) 값으로 저장. (재귀함수 형태로)
}

 

4. 코드

public class BaekJun1943Book {
    static int[] parent;
    static int[] trueP;
    static ArrayList<Integer>[] party;
    static int result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();
        result = 0;
        trueP = new int[T];

        for (int i = 0; i < T; i++) { // 진실을 아는 사람 저장
            trueP[i] = sc.nextInt();
        }

        party = new ArrayList[M];
        for (int i = 0; i < M; i++) { // 파티 데이터 저장
            party[i] = new ArrayList<>();
            int party_size = sc.nextInt();
            for (int j = 0; j < party_size; j++) {
                party[i].add(sc.nextInt());
            }
        }

        parent = new int[N + 1];
        for (int i = 0; i <= N; i++) { // 대표 노드를 자기 자신으로 초기화
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) { // 각 파티에 참여한 사람들을 1개의 그룹으로 만들기
            int firstPerson = party[i].get(0);
            for (int j = 1; j < party[i].size(); j++) {
                union(firstPerson, party[i].get(j));
            }
        }

        // 각 파티의 대표 노드와 진실을 아는 사람들의 대표 노드가 같다면 과장할 수 없음.
        for (int i = 0; i < M; i++) {
            boolean canLie = true;
            int firstPerson = party[i].get(0);
            for (int j = 0; j < trueP.length; j++) {
                if (find(firstPerson) == find(trueP[j])) {
                    canLie = false;
                    break;
                }
            }
            if (canLie) {
                result++;
            }
        }
        System.out.println(result);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    static int find(int node) {
        if (node == parent[node]) {
            return node;
        } else {
            return parent[node] = find(parent[node]);
        }
    }
}