[JAVA] 백준 union find 부수기(1)

 

 

 

 

24542 튜터-튜티 관계의 수 - 실버1

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

 

public class Main {
    static int[] parent;
    static int[] countArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //사이클 없는 그래프
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());
        int relationCnt = Integer.parseInt(st.nextToken());

        countArr = new int[count];
        parent = new int[count];
        for (int i = 0; i < count; i++) {
            parent[i] = i;
            countArr[i] = 1;
        }

        for (int i=0; i<relationCnt; i++) {
            st=  new StringTokenizer(br.readLine());

            int a= Integer.parseInt(st.nextToken())-1;
            int b= Integer.parseInt(st.nextToken())-1;

            union1(a, b);
        }

        long result = 1;
        for (int i = 0; i < count; i++) {
            if (parent[i] == i) {
                result = (result * countArr[i]) % 1_000_000_007;
            }
        }

        System.out.println(result);
    }

    private static int find(int a) {
        int parentA= parent[a];

        if (parentA == a) {
            return a;
        }

        parent[a] = find(parentA);

        return parent[a];
    }

    private static void union1(int a, int b) {
        int parentA = find(a);
        int parentB= find(b);

        parent[parentB] = parentA;
        countArr[parentA] += countArr[parentB];
    }
}

• bfs로도 충분히 구할 수 있지만, 유니온파인드로 풀어봤다
• 원래는 결과를 출력할 때 하나하나 find()를 호출해서 답을 구했는데, union과정에서 countArr값을 갱신시키는 풀이를 참고하여 조금 더 시간을 줄였다

 

 

 

1717 집합의 표현 - 골드5

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

public class Main {
    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 cnt = Integer.parseInt(st.nextToken());
        int operationCnt = Integer.parseInt(st.nextToken());
        parent = new int[cnt+1];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        for (int i=0; i<operationCnt; i++) {
            st = new StringTokenizer(br.readLine());
            if (st.nextToken().charAt(0) == '0') {
                //합집합연산
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                parent[find(a)] = parent[find(b)];
            } else {
                //포함여부 확인
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                if (find(a) == find(b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    public static int find(int a) {
        int parentA = parent[a];

        if (parentA == a) {
            return a;
        }

        parent[a] = find(parentA);
        return parent[a];
    }
}

• 그냥 union과 find를 잘 계산하면 되는 문제이다

 

 

7511 Constellations - 골드5

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

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();

        BufferedReader br  =new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine())+1;

        for (int t=1; t<tcCnt; t++) {
            sb.append("Scenario " + t + ":").append("\n");

            int userCnt = Integer.parseInt(br.readLine());
            int relationCnt = Integer.parseInt(br.readLine());
            parent = new int[userCnt+1];
            initParent();

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

                parent[find(a)] = parent[find(b)];
            }

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

                if (find(a) == find(b)) {
                    sb.append("1").append("\n");
                } else {
                    sb.append("0").append("\n");
                }
            }
            
            sb.append("\n");
        }

        System.out.print(sb);
    }

    private static void initParent() {
        for (int i=1; i<parent.length; i++) {
            parent[i] = i;
        }
    }

    private static int find(int a) {
        int parentA = parent[a];

        if (parentA == a) {
            return a;
        }

        parent[a] = find(parentA);
        return parent[a];
    }
}

• 응용도 하나도 없는 단순 union find 문제다
• 골드5는 응용이 없는 것 같아 골드4로 넘어가야겠다

 

 

 

 

10216 Count Circle Groups - 골드4

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

public class Main {
    static int[][] info;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        for (int t=0; t<tcCnt; t++) {
            int nodeCnt = Integer.parseInt(br.readLine());

            parent = new int[nodeCnt];
            info  = new int[nodeCnt][3];

            for (int i =0; i<nodeCnt; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int r= Integer.parseInt(st.nextToken());
                info[i] = new int[]{x,y,r};
                parent[i] = i;
            }

            //거리 하나하나 비교, union
            for (int i =0; i<info.length-1; i++) {
                for (int j=i+1; j<info.length; j++) {
                    if (canUnion(i ,j)) {
                        int parentI = findParent(i);
                        int parentJ = findParent(j);

                        if (parentI != parentJ) {
                            parent[parentI] = parent[parentJ];
                        }
                    }
                }
            }

            int result = 0;
            for (int i =0; i<parent.length; i++) {
                if (parent[i] == i) {
                    result ++;
                }
            }

            System.out.println(result);
        }
    }

    private static boolean canUnion(int i, int j) {
        int dx = info[i][0] - info[j][0];
        int dy = info[i][1] - info[j][1];

        int r = info[i][2] + info[j][2];
        if (dx*dx + dy*dy > r*r) {
            return false;
        }

        return true;
    }

    private static int findParent(int a) {
        if (parent[a] != a) {
            parent[a] = findParent(parent[a]);
        }

        return parent[a];
    }
}

• 좌표간의 거리 공식만 알면 어렵지않게 풀 수 있는 문제다

 

 

13905 세부  - 골드4

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

class Node implements Comparable<Node> {
    int num1;
    int num2;
    int value;

    public Node(int num1, int num2, int value) {
        this.num1 = num1;
        this.num2 = num2;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return -Integer.compare(this.value, o.value);
    }
}

public class Main {
    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 houseCnt = Integer.parseInt(st.nextToken());
        int bridgeCnt = Integer.parseInt(st.nextToken());

        parent = new int[houseCnt + 1];
        for (int i =1; i<parent.length; i++) {
            parent[i] = i;
        }

        st = new StringTokenizer(br.readLine());
        int sung = Integer.parseInt(st.nextToken());
        int hye = Integer.parseInt(st.nextToken());

        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (int i = 0; i < bridgeCnt; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int limit = Integer.parseInt(st.nextToken());

            pq.add(new Node(a, b, limit));
        }

        int result  = 0;
        while (!pq.isEmpty()) {
            Node poll = pq.poll();

            if (find(poll.num1) == find(poll.num2)) {
                continue;
            }

            int parent1 = parent[poll.num1];
            int parent2 = parent[poll.num2];

            parent[parent1] = parent[parent2];

            if (find(sung) == find(hye)) {
                result = poll.value;
                break;
            }
        }

        System.out.println(result);
    }

    public static int find(int x) {
        int parentX = parent[x];

        if (parentX != x) {
            parent[x] = find(parentX);
            return parent[x];
        }

        return parent[x];
    }
}

• 다익스트라로 풀고싶었지만, 유니온파인드를 사용하기 위해 크루스칼을 사용하였다
• value가 큰 간선으로 정렬되어있기 때문에, 만나는 순간의 가중치가 가지고 갈 수 있는 최대 값이 된

 

 

 

16562 친구비  - 골드4

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

public class Main {
    static int[] parent;
    static int[] cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int studentCnt = Integer.parseInt(st.nextToken());
        int relationCnt = Integer.parseInt(st.nextToken());
        int money = Integer.parseInt(st.nextToken());

        parent = new int[studentCnt+1];
        cost = new int[studentCnt+1];

        st = new StringTokenizer(br.readLine());
        for (int i=1; i<cost.length; i++) {
            parent[i] = i;
            cost[i] = Integer.parseInt(st.nextToken());
        }

        for (int i =0; i<relationCnt; i++) {
            st = new StringTokenizer(br.readLine());
            union(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }

        //10_000 * 10_000 = 100_000_000
        int requiredMoney = 0;
        for (int i =1; i<parent.length; i++) {
            if (parent[i] == i) {
                requiredMoney += cost[i];
            }
        }

        if (money < requiredMoney) {
            System.out.println("Oh no");
        } else {
            System.out.println(requiredMoney);
        }
    }

    public static void union(int a, int b) {
        int parentA= find(a);
        int parentB= find(b);

        if (parentA == parentB) {
            return;
        }

        if (parentA < parentB) {
            parent[parentB] = parentA;
            cost[parentA] = Math.min(cost[parentA], cost[parentB]);
        } else {
            parent[parentA] = parentB;
            cost[parentB] = Math.min(cost[parentA], cost[parentB]);
        }
    }

    static int find(int x) {
        int parentX = parent[x];

        if (parentX == x) {
            return x;
        }

        parent[x] = find(parentX);
        return parent[x];
    }
}

• 같은 그룹 내에서 가장 작은 친구비를 cost 배열에 저장해두고 출력해주는 방법을 사용하였다
• union find만 안다면 어렵지 않은 문제다

 

 

16724 피리 부는 사나이 - 골드3

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

public class Main {
    static int[] rowStep = {-1, 1, 0, 0};
    static int[] colStep = {0, 0, -1, 1};
    static int[][][] parent;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int rowCnt = Integer.parseInt(st.nextToken());
        int colCnt = Integer.parseInt(st.nextToken());

        map = new int[rowCnt + 2][colCnt + 2];
        parent = new int[map.length][map[0].length][2];
        for (int i = 0; i < map.length; i++) {
            map[i][0] = -1;
            map[i][map[0].length - 1] = -1;
        }

        for (int i = 0; i < map[0].length; i++) {
            map[0][i] = -1;
            map[map.length - 1][i] = -1;
        }

        int idx = 1;
        int bound1 = map.length - 1;
        int bound2 = map[0].length - 1;
        for (int i = 1; i < bound1; i++) {
            String input = br.readLine();
            for (int j = 1; j < bound2; j++) {
                char c = input.charAt(j-1);
                if (c == 'U') {
                    map[i][j] = 0;
                } else if (c == 'D') {
                    map[i][j] = 1;
                } else if (c == 'L') {
                    map[i][j] = 2;
                } else if (c == 'R') {
                    map[i][j] = 3;
                }
                parent[i][j][0] = i;
                parent[i][j][1] = j;
            }
        }

        for (int i=1; i<bound1; i++) {
            for (int j= 1; j<bound2; j++) {
                int dir = map[i][j];
                int tmpRow = i + rowStep[dir];
                int tmpCol = j + colStep[dir];

                if (map[tmpRow][tmpCol] == -1) {
                    continue;
                }

                union(i, j, tmpRow, tmpCol);
            }
        }

        System.out.println(rowCnt * colCnt - tmp);
    }

    static int tmp=0;

    private static void union(int row, int col, int nextRow, int nextCol) {
        int parentARow = parent[row][col][0];
        int parentACol = parent[row][col][1];
        int parentBRow = parent[nextRow][nextCol][0];
        int parentBCol = parent[nextRow][nextCol][1];

        int[] a = find(parentARow, parentACol);
        int[] b = find(parentBRow, parentBCol);

        if (a[0] == b[0] && a[1] == b[1]) {
            return;
        }

        parent[a[0]][a[1]][0] = parent[b[0]][b[1]][0];
        parent[a[0]][a[1]][1] = parent[b[0]][b[1]][1];
        tmp++;
    }

    private static int[] find(int row, int col) {
        int[] parentA = parent[row][col];

        if (parentA[0] == row && parentA[1] == col) {
            return new int[]{row, col};
        }

        parent[row][col] = find(parentA[0], parentA[1]);
        return parent[row][col];
    }
}

• 연결되는 집합 내에서 하나의 safezone을 만들 수 있다
• union find를 사용하여 어떤 집합에 포함되는지 체크해주고, 집합의 개수를 세주면 safezone의 개수가 된다.
• 2차원 배열 union find는 처음이라 참신했다. 나는 부모를 저장하기 위해 3차원 배열을 사용했는데, 더 좋은 풀이가 많을 것 같다

 

16957 체스판 위의 공 - 골드3

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

public class Main {
    static int[] rowStep = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] colStep = {0, 0, -1, 1, -1, 1, -1, 1};
    static int[][][] parent;
    static int[][] cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int rowSize = Integer.parseInt(st.nextToken());
        int colSize = Integer.parseInt(st.nextToken());

        int[][] arr = new int[rowSize + 2][colSize + 2];
        parent = new int[rowSize + 2][colSize + 2][2];
        cnt = new int[rowSize + 2][colSize + 2];

        //-1로 둘러싸기
        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = -1;
            arr[i][arr[0].length - 1] = -1;
        }
        for (int i = 0; i < arr[0].length; i++) {
            arr[0][i] = -1;
            arr[arr.length - 1][i] = -1;
        }

        int bound1 = arr.length - 1;
        int bound2 = arr[0].length - 1;
        for (int i = 1; i < bound1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < bound2; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                parent[i][j] = new int[]{i, j};
                cnt[i][j] = 1;
            }
        }

        for (int i = 1; i < bound1; i++) {
            for (int j = 1; j < bound2; j++) {
                int minValue = arr[i][j];
                int minRow = 0;
                int minCol = 0;
                for (int step = 0; step < rowStep.length; step++) {
                    int tmpRow = i + rowStep[step];
                    int tmpCol = j + colStep[step];

                    if (arr[tmpRow][tmpCol] == -1) {
                        continue;
                    }

                    if (minValue > arr[tmpRow][tmpCol]) {
                        minValue = arr[tmpRow][tmpCol];
                        minRow = tmpRow;
                        minCol = tmpCol;
                    }
                }

                if (minValue == arr[i][j]) {
                    continue;
                }

                int[] parentA = find(minRow, minCol);
                cnt[parentA[0]][parentA[1]] += cnt[parent[i][j][0]][parent[i][j][1]];
                cnt[parent[i][j][0]][parent[i][j][1]] = 0;
                parent[i][j][0] = parentA[0];
                parent[i][j][1] = parentA[1];
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < bound1; i++) {
            for (int j = 1; j < bound2; j++) {
                sb.append(cnt[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }

    public static int[] find(int row, int col) {
        int[] myParent = parent[row][col];

        if (myParent[0] == row && myParent[1] == col) {
            return new int[]{row, col};
        }

        parent[row][col] = find(myParent[0], myParent[1]);
        return parent[row][col];
    }
}

• 문제가 굉장히 재미있었다
• 공이 한 그룹 내의 가장 작은 값으로 굴러떨어진다고 생각했을 때, 매번 dfs나 bfs를 사용하면 비효율적이다
• 이 때 union find 개념을 이용하면 굉장히 어렵지 않게 풀 수 있었다