[코테연습] 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

- union-find, graph 문제

UnionFind 문제는 1. 문제파악 => UnionFind 문제 확인 / 2. UnionFindClass 구현
단계로 나누어 풀어야한다.

- UnionFindClass 구현
1. 전역변수 int[] root 초기화
2. constructor 시, root 값 n+1 로 자기 자신으로 초기화 하기
 2-1. root = new int[n+1] 
 2-2. for in root[i] = i;
3. find() 함수 구현
 3-1. find() 함수 구현시 경로압축 구현하여 속도 향상 ( return root[x] = find(root[x]) )
4. union() 함수 구현
 4-1. 같은 계층인지 확인하여 return (x == y)
 4-2. 다른 계층 일 경우 root[y] = x 구현
 

 

 

https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/description/?envType=daily-question&envId=2024-06-30

 

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind alice = new UnionFind(n);//alice root = [1,2,3,4]
        UnionFind bob = new UnionFind(n);//bob root = [1,2,3,4]

        int edgesRequired = 0;//연결에 필요한 간선의 갯수를 구하기 위한 변수
        for (int[] edge: edges) {
            int type = edge[0];
            int v = edge[1];
            int u = edge[2];
            if (type == 3) {
                int _a = alice.union(v, u);
                int _b = bob.union(v, u);
                edgesRequired += (_a | _b);//둘중 하나라도 연결되었을 경우, 1을 반환하여 연결에 필요한 간선의 갯수를 더해준다.
            }
        }
        //type 3 에만 해당하는 edge 의 노드 값을 연결하였음
        /*
         * alice = [1,1,1,4]
         * bob = [1,1,1,4]
         * edgesRequired = 2
         */


        //type 1 일경우에는 alice 연결을, type 2일경우에는 bob 연결을 위한 반복문.
        for (int[] edge:edges) {
            int type = edge[0];
            int v = edge[1];
            int u = edge[2];
            if (type == 1) {
                edgesRequired += alice.union(v,u);//alice 의 간선이 연결되었을 경우 1 반환
            } else if ( type == 2) {
                edgesRequired+= bob.union(v, u);//bob 의 간선이 연결되었을 경우 1 반환.
            }
        }
        //각자 alice, bob 의 모든 간선이 연결되었을 경우 필요한 간선의 갯수는 edgesRequired 에 담겨있다.
        //총 연결된 간선에서 필요한 간선을 빼준다.
        if (alice.isConnected() && bob.isConnected()) {
            int rs = edges.length-edgesRequired;
            return rs;
        }
        //연결되지 않았을 경우 -1 을 리턴
        return -1;
    }
     //UnionFind class 만들기
    class UnionFind {
        //초기화할 root Node
        int[] root;
        //연결 여부를 확인할 connect
        int connect;
        //constructor
        public UnionFind(int n){
            //간선(n) 만큼, 연결 connect count 를 초기화
            connect = n;
            //rootNode 에는 자기 자신이 초기화 되어있다. root[] ={1,2,3,4}
            root = new int[n+1];
            for(int i = 0; i <= n; i++) {
                root[i] = i;
            }
        }
        //각자의 root 값을 찾기위한 함수
        /*
         * {1,2},{2,3} 
         * find (1) => root[1] == 1 return 1;
         * find (2) => root[2] == 2 return 2;
         * 
         * find (2) => root[2] == 2 return 2;
         * find (3) => root[3] == 3 return 3;
         */
        int find(int x){
            if (root[x] == x) {
                return x;
            } else {
                // "경로 압축(Path Compression)"
                // find 하면서 만난 모든 값의 부모 노드를 root로 만든다.
                return root[x] = find(root[x]);
            }
        }
        //x,y 값을 합쳐 같은 Node로 변환한다.
        /*
         * {1,2},{2,3}
         * union(1,2) => 1 = find(1) = 1
         *            => 2 = find(2) = 2
         * root[2] = 1;
         * [1,2,3,4] => [1,1,3,4]
         * 
         * union(2,3) => 2 = find(2) = 1
         *            => 3 = find(3) = 3;
         * root[3] = 1;
         * [1,1,3,4] => [1,1,1,4]
         */
        int union (int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return 0;
            }
            //연결되었을 경우 연결 완료된 간선을 지운다.
            connect--;
            root[y] = x;
            return 1;
        }

        boolean isConnected(){
            return connect == 1;
        }
    }
}

 

 

==== 백준 문제 모음

 

https://www.acmicpc.net/workbook/view/900