[알고리즘] 유니온 파인드(백준 1717, 1976, 1043, 4195, 20040 -Java)

[알고리즘] 유니온 파인드(백준 1717, 1976, 1043, 4195, 20040)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

유니온 파인드

 

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

 

✅ 방향이 없는(무방향) 그래프에서 사용 가능합니다.

 

• 루트 노드가 서로 다르다면 두 노느에 대하여 합집합(Union) 연산을 수행
• find 연산을 통해 루트 노드가 서로 같다면 사이클(Cycle) 발생

 

유니온 파인드 핵심 이론

유니온 파인드는 union, find 연산을 완벽히 이해해야 합니다.

Union 연산
각 노드가 속한 집합을 1개로 합치는 연산
노드 a가 A집합에 속하고, 노드 b가 B 집합에 속할 때
Union 연산은 A와 B의 합집합을 의미합니다.

 

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

 

유니온 파인드 구현 방법

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

 

이제 union 연산을 해보자!
union(1, 4)를 해보자!
union 연산에서 중요한 것은 항상 대표 노드 끼리 연결해주는 것 입니다.

 

union(5, 6)를 해보자!

 

여기서 union(4, 6)을 하면 어떻게 될까요? 🤔
앞에서 이야기 한것 처럼 union 연산에서 중요한 것은 항상 대표 노드 끼리 연결해주는 것 입니다.!!!!!!!!!!!
대표 노드를 찾기 위해서는 find 연산을 수행해야 합니다.

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

 

Find 연산 작동원리

1) 대상 노드 배열에 index값과 value값이 동일한지 확인
2) 동일하지 않으면 value가 가리키는 index로 이동
3) 동일할 때 까지 1, 2 반복합니다.(동일하면 그 값이 대표 노드 👍)
4) ✅ 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경

 

여기서 find(6)을 해보자!

✅ 대표 노드에 도달한 후
재귀 함수를 빠져나오면서
거치는 모든 노드값을 대표 노드값으로 변경해야 합니다.!!

 

근데 이렇게 왜 해야할까요? 🤔
아까 제가 find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상 시킵니다.^^ 라고 이야기 했습니다.!!
감이 오시나요?

find 연산에서 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드값으로 변경하지 않으면,
나중에 find(6)을 다시 할 때, 대표 노드(1)가 있는 곳까지 또!!! 탐색을 해야 합니다.
이건 ⏰ 시간 낭비입니다.!

 

유니온 파인드는 우리가 탐색을 원하는 노드끼리 연결(무방향) 되어있는지 아닌지만 알면 됩니다!!!!

백준 1717

1717번: 집합의 표현
유니온 파인드의 기본적인 문제 입니다.

 

풀이

public class Quiz1717 {
    /**
     *  0 ~ n이 있을때
     *  합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지 확인하는 코드 작성
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 0 ~ n
        int n = Integer.parseInt(st.nextToken());
        // 연산 횟수
        int m = Integer.parseInt(st.nextToken());

        // 대표노드 배열 생성 및 초기화
        int[] ceoArr = new int[n+1]; // 0부터 n까지
        // 초기화(index를 대표노드로 설정)
        for(int i = 0; i < ceoArr.length; i++) {
            ceoArr[i] = i;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int condition = Integer.parseInt(st.nextToken());
            int index1 = Integer.parseInt(st.nextToken());
            int index2 = Integer.parseInt(st.nextToken());

            if(condition == 0) {
                // union 연산
                union(ceoArr, index1, index2);
            } else if(condition == 1) {
                // find 연산
                if(find(ceoArr, index1) == find(ceoArr, index2)) {
                    sb.append("YES").append("\n");
                } else {
                    sb.append("NO").append("\n");
                }
            }
        }
        System.out.print(sb);
        br.close();
    }

    // 대표 노드를 설정 해준다.
    private static void union(int[] ceoArr, int index1, int index2) {
        // index의 대표 노드 반환
        int ceoNode1 = find(ceoArr, index1);
        int ceoNode2 = find(ceoArr, index2);

        // 대표노드가 다르면 대표노드 중 작은 값으로 대표노드로 설정
        if(ceoNode1 != ceoNode2) {
            if(ceoNode1 > ceoNode2) {
                ceoArr[ceoNode1] = ceoNode2;
            } else {
                ceoArr[ceoNode2] = ceoNode1;
            }
        }
    }

    // 대표 노드 반환
    private static int find(int[] ceoArr, int index) {
        // index의 대표노드와 index와 같으면
        if(index == ceoArr[index]) {
            // index가 대표노드!
            return index;
        }
        // index의 대표노드와 index와 다르면
        // ceoArr[index]를 index로 해서 대표 노드를 찾고
        // find 전 index의 대표노드로 갱신 해준다.
        return ceoArr[index] = find(ceoArr, ceoArr[index]);
    }
}

백준 1976

1976번: 여행 가자

유니온 파인드를 사용해서 대표노드가 같은지 확인하면 됩니다.
그러면 여행을 갈 수 있습니다.^^

 

입력

3        // 도시의 수
3        // 여행예정 도시 수
0 1 0    // 1번 도시는 2번 도시만 연결
1 0 1    // 2번 도시는 1, 3번 도시만 연결
0 1 0    // 3번 도시는 2번 도시와 연결
1 2 3    // 여행 계획 도시번호

 

풀이

public class Quiz1976 {
    /**
     * 3        // 도시의 수
     * 3        // 여행예정 도시 수
     * 0 1 0    // 1번 도시는 2번 도시만 연결
     * 1 0 1    // 2번 도시는 1, 3번 도시만 연결
     * 0 1 0    // 3번 도시는 2번 도시와 연결
     * 1 2 3    // 여행 계획 도시번호
     */

    public static void main(String[] args) throws IOException {
        /**
         * 유니온 파인드를 이용해서 대표노드를 설정한다.
         * 대표노드가 같으면 여행 계획이 가능하다!
         *
         * 왜냐하면, 대표노드가 같다는 것은
         * 선택한 여행지(노드1)에서 다른 여행지(노드2)는 대표 노드를 통하면 갈 수 있다는 의미
         * 즉, 대표노드가 같으면 노드끼리 서로 연결되어 있다는 의미!!
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 도시 수
        int n = Integer.parseInt(br.readLine());
        // 여행 예정 도시 수
        int m = Integer.parseInt(br.readLine());

        // 도시는 1번부터 시작
        int[] arr = new int[n+1];
        // 대표 도시 배열 생성, 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        // i 번째 도시
        for(int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // j 번째 도시
            for(int j = 1; j <= n; j++) {
                int comm = Integer.parseInt(st.nextToken());
                // i번째 도시와 j번째 도시가 같지 않은 경우만 고려하면 된다.
                if(i != j) {
                    if(comm == 1) {
                        // 연결관계를 보고 대표노드 설정
                        union(arr, i, j);
                    }
                }
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 여행계획 도시
        int[] cityTour = new int[m];
        for(int i = 0; i < m; i++) {
            cityTour[i] = Integer.parseInt(st.nextToken());
        }

        // 첫 번째 여행계획 도시의 대표노드
        int ceoNode = find(arr, cityTour[0]);
        for(int i = 1; i < m; i++) {
            // 첫 번째 여행계획 도시의 대표노드와 i번째 여행가능 도시의 대표노드가 다르면
            if(ceoNode != find(arr, cityTour[i])) {
                // 여행계획으로 여행 불가!
                System.out.print("NO");
                br.close();
                return;
            }
        }

        // 여행 가능^^
        System.out.print("YES");
        br.close();
    }

    // 대표 노드 설정
    private static void union(int[] arr, int i, int j) {
        int ceoNode1 = find(arr, i);
        int ceoNode2 = find(arr, j);

        // 값이 작은 값으로 대표노드 설정
        if(ceoNode1 != ceoNode2) {
            if(ceoNode1 > ceoNode2) {
                arr[ceoNode1] = ceoNode2;
            } else {
                arr[ceoNode2] = ceoNode1;
            }
        }
    }

    // 대표 노드 반환
    private static int find(int[] arr, int node) {
        // index와 node값이 같으면
        if(arr[node] == node) {
            // index가 곧 대표노드
            return node;
        }
        return arr[node] = find(arr, arr[node]);
    }
}

백준 1043

1043번: 거짓말

입력 값이 복잡해서 스스로 해결하지 못했다..
여기서 중요한 부분은 거짓말인지 아는 사람을 저장하는 배열이라고 생각합니다.
이때 배열의 인덱스에 거짓말을 아는 사람 번호로 저장합니다.

// 거짓말인지 아는 사람 번호
boolean[] knowMan = new boolean[n+1];
for(int i = 0; i < count; i++) {
    int num = Integer.parseInt(st.nextToken());
    // index가 사람 번호
    knowMan[num] = true;
}

 

그리고 중요한게
파티에 참가하는 사람들의 번호를 저장하는 입력부라고 생각합니다.
사실 이 부분이 제일 어려웠습니다…

// 이전 입력 값
// e.g) 2 1 2 가 입력이면
int prev = 0;
for(int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine());
    // 파티에 오는 사람 수
    // 2
    int num = Integer.parseInt(st.nextToken());
    if(num > 0) {
        // 1
        prev = Integer.parseInt(st.nextToken());
        party[i].add(prev);
    }
    // num이 2 이기때문에 for문으로 들어간다
    for(int j = 1; j < num; j++) {
        // 2
        int current = Integer.parseInt(st.nextToken());
        party[i].add(current);
        // 같이 파티에 온 사람을 동일한 대표노드로 묶어 버린다.
        union(arr, prev, current);
        // 이전 입력값에 현재 입력값을 넣어줘서 이전 입력값으로 만든다.
        prev = current; // 2
    }
}

 

풀이

package backjoon.graph.union_find;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Quiz1043 {
    /**
     * 지민이는 파티에 참가
     * 파티에는 지민이가 거짓말인지 아닌지 아는 사람이 있을 수도 없을 수도 있음
     * 거짓말을 아는 사람이 1명이라도 있을 경우 지민이는 해당 파티에서 진실만을 이야기 해야 한다.
     * 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다
     *
     * 지민이가 진실만 이야기하는 파티의 최대 갯수
     */
    public static void main(String[] args) throws IOException {
        /**
         * 4 2          // 사람 수(4), 파티 수(2)
         * 1 1          // 거짓말인지 아는 사람의 수(1), 거짓말인지 아는 사람 번호(1)
         * 4 1 2 3 4    // 파티에 오는 사람 수(4), 파티에 오는 사람 번호(1, 2, 3, 4)
         * 3 1 2 3      // 파티에 오는 사람 수(3), 파티에 오는 사람 번호(1, 2, 3)
         */
        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());

        st = new StringTokenizer(br.readLine());
        // 거짓말인지 아는 사람의 수
        int count = Integer.parseInt(st.nextToken());

        // 거짓말인지 아는 사람 번호
        boolean[] knowMan = new boolean[n+1];
        for(int i = 0; i < count; i++) {
            int num = Integer.parseInt(st.nextToken());
            // index가 사람 번호
            knowMan[num] = true;
        }

        // 대표 노드 배열 생성 및 초기화
        int[] arr = new int[n+1];
        for(int i = 1; i < arr.length; i++) {
            arr[i] = i;
        }

        // 파티 생성
        List<Integer>[] party = new ArrayList[m];
        for(int i = 0; i < m; i++) {
            party[i] = new ArrayList<>();
        }

        // 이전 입력 값
        // e.g) 2 1 2 가 입력이면
        int prev = 0;
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            // 파티에 오는 사람 수
            // 2
            int num = Integer.parseInt(st.nextToken());
            if(num > 0) {
                // 1
                prev = Integer.parseInt(st.nextToken());
                party[i].add(prev);
            }
            // num이 2 이기때문에 for문으로 들어간다
            for(int j = 1; j < num; j++) {
                // 2
                int current = Integer.parseInt(st.nextToken());
                party[i].add(current);
                // 같이 파티에 온 사람을 동일한 대표노드로 묶어 버린다.
                union(arr, prev, current);
                // 이전 입력값에 현재 입력값을 넣어줘서 이전 입력값으로 만든다.
                prev = current; // 2
            }
        }

        // 거짓말인지 아는 사람의 수가 0이면
        if(count == 0) {
            // 모든 파티에서 거짓말 가능
            System.out.print(m);
            br.close();
            return;
        }

        // 진실을 아는 사람들과 같이 파티를 참여했다면 그 사람도 진실을 알게됨
        for(int i = 1; i < knowMan.length; i++) {
            if(knowMan[i]) {
                // i가 진실을 아는 사람의 번호
                // i의 대표노드에 있는 사람도 진실을 알게 된다.
                knowMan[find(arr, i)] = true;
            }
        }

        // 진실을 아는 사람들과 파티를 같이 하지 않은 경우 구하기
        int result = 0;
        // 파티 탐색
        for(int i = 0; i < m; i++) {
            // i 번째 파티에 있는 인원 탐색
            for(int j = 0; j < party[i].size(); j++) {
                // 해당 파티의 사람의 대표노드를 꺼낸다.
                int ceoNode = find(arr, party[i].get(j));
                // 진실을 아는 사람이면
                if(!knowMan[ceoNode]) {
                    result++;
                    // 해당 파티에서는 거짓을 더이상 말하지 못하기 때문에 탈출!
                    break;
                }
            }
        }

        System.out.print(result);
        br.close();
    }

    // 대표 노드 설정
    private static void union(int[] arr, int index1, int index2) {
        // index의 대표 노드 반환
        int ceoNode1 = find(arr, index1);
        int ceoNode2 = find(arr, index2);

        // 대표노드가 다르면 대표노드 중 작은 값으로 대표노드로 설정
        if(ceoNode1 != ceoNode2) {
            if(ceoNode1 > ceoNode2) {
                arr[ceoNode1] = ceoNode2;
            } else {
                arr[ceoNode2] = ceoNode1;
            }
        }
    }

    // 대표 노드 반환
    private static int find(int[] arr, int index) {
        // index의 대표노드와 index와 같으면
        if(arr[index] == index) {
            // index가 대표노드!
            return index;
        } else {
            // index의 대표노드와 index와 다르면
            // ceoArr[index]를 index로 해서 대표 노드를 찾고
            // find 전 index의 대표노드로 갱신 해준다.
            return arr[index] = find(arr, arr[index]);
        }
    }
}

백준 4195

4195번: 친구 네트워크

처음에 시간초과가 발생해서 해결하지 못했습니다… ㅠㅠ
문제의 핵심은 대표 친구의 네트워크에 있는 친구 숫자를 저장하는 count라는 배열을 만들어서
union(친구1, 친구2)할 때 (단, 여기서 항상 친구1 < 친구2)
친구1의 대표 친구에 친구2의 대표 친구의 네트워크에 있는 친구 숫자를 더해줘야 합니다.

 

입력이 아래라고 가정하고 진행해보겠습니다.

Fred Barney
Betty Wilma
Barney Betty

Fred -> 0, Barney -> 1, Betty -> 2, Wilma -> 3 라고 하겠습니다.

 

그러면 입력은 다음과 같다고 생각할 수 있습니다.

0 1
2 3
1 2

 

이를 그림으로 설명하면 다음과 같습니다.

 

이를 코드로 보면 다음과 같습니다.^^

// 친구 네트워크 형성
private static int union(int[] parent, int[] count, int pk1, int pk2) {
    // 대표 친구 번호
    int friend1 = find(parent, pk1);
    int friend2 = find(parent, pk2);

    // 대표 친구가 다르면 대표 친구 번호가 작은순으로 설정(항상 friend1 < friend2)
    if(friend1 != friend2) {
        parent[friend2] = friend1;
        // friend2에 있는 친구의 숫자를 더해줌
        count[friend1] += count[friend2];
        // friend2에 있는 친구 숫자를 1로 초기화
        count[friend2] = 1;
    }
    // 대표노드의 친구 수 반환
    return count[friend1];
}

 

풀이

public class Quiz4195 {
    public static void main(String[] args) throws IOException {
        /**
         * 친구 관계가 생긴 순서대로 입력값이 주어진다.
         * 두 사람의 친구 네트워크에 몇 명이 있는지 출력
         *
         * *친구 네트워크란 친구 관계만으로 이동할 수 있음
         * 즉, 다른 사람이 동일한 친구를 관계가 있다면 친구 네트워크
         * 서로 다른 사람(노드)이 친구(대표노드)가 같으면 친구네트워크!
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // 테스트 케이스
        int testCase = Integer.parseInt(br.readLine());
        for(int t = 0; t < testCase; t++) {
            // 친구 관계 수
            int frc = Integer.parseInt(br.readLine());

            // 친구 배열<친구 아이디, 친구 고유 번호>
            // 친구를 고유 번호로 표현하기 위함.
            Map<String, Integer> friends = new HashMap<>();
            // 친구 고유 번호
            int pk = 0;

            // 대표친구 고유 번호 배열 초기화
            int[] parent = new int[frc*2];
            // 네트워크에 있는 친구 수
            int[] count = new int[frc*2];
            for(int i = 0; i < parent.length; i++) {
                parent[i] = i;
                count[i] = 1; // 친구 네트워크에는 처음에 혼자이기 때문에 1로 초기화
            }

            // 친구 아이디
            String[] ids = new String[frc];
            for(int f = 0; f < frc; f++) {
                ids[f] = br.readLine();
                String[] id = ids[f].split(" ");

                // key, value 형태로 친구id, pk
                // 친구 id가 없다면
                if(!friends.containsKey(id[0])) {
                    friends.put(id[0], pk++);
                }
                if (!friends.containsKey(id[1])) {
                    friends.put(id[1], pk++);
                }

                // 친구 네트워크 형성
                int result = union(parent, count, friends.get(id[0]), friends.get(id[1]));

                // 친구 네트워크에 있는 친구 수 세기
                sb.append(result).append("\n");
            }
        }
        System.out.print(sb);
        br.close();
    }

    // 친구 네트워크 형성
    private static int union(int[] parent, int[] count, int pk1, int pk2) {
        // 대표 친구 번호
        int friend1 = find(parent, pk1);
        int friend2 = find(parent, pk2);

        // 대표 친구가 다르면 대표 친구 번호가 작은순으로 설정(항상 friend1 < friend2)
        if(friend1 != friend2) {
            parent[friend2] = friend1;
            // friend2에 있는 친구의 숫자를 더해줌
            count[friend1] += count[friend2];
            // friend2에 있는 친구 숫자를 1로 초기화
            count[friend2] = 1;
        }
        // 대표노드의 친구 수 반환
        return count[friend1];
    }

    // 대표 친구 고유 번호 찾기
    private static int find(int[] parent, int pk) {
        if(parent[pk] == pk) {
            return pk;
        } else {
            return parent[pk] = find(parent, parent[pk]);
        }
    }
}

백준 20040

20040번: 사이클 게임
유니온 파인드의 기본 개념을 알면 해결할 수 있는 문제 입니다.
union과정에서find를 하는데 이때 find(노드1) == find(노드2) 이면 사이클이 발생한것 입니다.^^

그림으로 설명하면 다음과 같습니다.

입력

6 5
0 1
1 2
1 3
0 3
4 5

 

 

 

풀이

public class Quiz20040 {
    /**
     * 선 플레이어가 홀수번째
     * 후 플레이어가 짝수번째
     * 평면상에 0 ~ n-1까지 고유한 번호 n개 부여
     * 사이클을 완성하면 게임 종료 -> 노드1, 노드2의 같으면 사이클이 생성!! 게임 종료
     *
     * union 과정에서 find를 하는데 이때 find(노드1) == find(노드2) 이면 사이클이 발생한것!
     */
    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());

        // 고유번호의 대표 노드 생성
        int[] parent = new int[n];
        for(int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int point1 = Integer.parseInt(st.nextToken());
            int point2 = Integer.parseInt(st.nextToken());

            boolean isCycle = union(parent, point1, point2);
            // 사이클 발생
            if(isCycle) {
                System.out.print(i+1);
                br.close();
                return;
            }
        }
        System.out.print(0);
        br.close();
    }

    private static boolean union(int[] parent, int point1, int point2) {
        int ceoNode1 = find(parent, point1);
        int ceoNode2 = find(parent, point2);
        // 대표노드가 다르면 대표노드를 작은것으로 설정
        if(ceoNode1 != ceoNode2) {
            if(ceoNode1 > ceoNode2) {
                parent[ceoNode1] = ceoNode2;
            } else {
                parent[ceoNode2] = ceoNode1;
            }
            // 사이클 발생 X
            return false;
        }
        // 대표노드가 같으면 사이클 발생
        return true;
    }

    private static int find(int[] parent, int point) {
        if(parent[point] == point) {
            return point;
        } else {
            return parent[point] = find(parent, parent[point]);
        }
    }
}