P.20040 사이클 게임

코드

package Baekjoon.Class;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class P_20040 {

    static int n, m;
    static ArrayList<Edge> edges = new ArrayList<>();
    static int[] parents;

    static public class Edge {
        int v1, v2;

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1];
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            edges.add(new Edge(line[0], line[1]));
        }

        parents = new int[n];
        for (int i = 0; i < n; i++) parents[i] = i;
        bw.write(Integer.toString(kruskal()));
        bw.flush();
    }

    private static int kruskal() {
        for (int i = 0; i < m; i++) {
            Edge edge = edges.get(i);

            if (!isSameParent(edge.v1, edge.v2))
                union(edge.v1, edge.v2);
            else return i + 1;
        }

        return 0;
    }

    private static void union(int v1, int v2) {
        int r1 = find(v1);
        int r2 = find(v2);

        if (r1 != r2) parents[r2] = r1;
    }

    private static int find(int v) {
        if (parents[v] == v) return v;
        else return parents[v] = find(parents[v]);
    }

    private static boolean isSameParent(int v1, int v2) {
        if (find(v1) == find(v2)) return true;

        return false;
    }
}

코드 설명

크루스칼 알고리즘을 이용했다.

크루스칼 알고리즘은 MST의 한 종류지만 이 문제에서는 union-find만 중점적으로 이용했다.

 

union함수에서 parents[v2] = r1이라고 쓰는 바람에 계속 틀렸다.원리 자체는 이해했는데 디테일이 부족한 것 같다.

 

union함수는 v1과 v2의 루트가 다르면 v2의 최상위 루트를 v1으로 맞춰주는 함수다.find함수로 각 vertex의 루트를 찾게 되는데 현재 find함수는 해당 vertex의 루트로 가는 길을 모두 변경을 해준다.

그럼 r1과 r2가 다르다는 의미는 뭘까? v1의 루트와 v2의 루트가 다르다는 것이다.

그렇다면 루트를 r1로 통합시켜주어야 하는데 v2의 루트의 루트를 설정하는 느낌이다.

그러니까 v2의 부모를 r1으로 바로 올려버리는 것이 아니라 v2의 루트였던 r2의 부모(루트)를 r1으로 올려줘야한다.

이 때 트리의 높이는 최소 2가 되겠다.

처음 코딩한 것처럼 v2의 부모를 r1으로 올려버리면 트리가 뚝 끊겨버리고 길이 두 개가 생겨버리는 비대칭 경로 느낌이 되어 버린다.