[알고리즘] 1717번

오늘 풀어볼 문제는 백준 1717번 문제이다.

문제

입력

출력

📌 도전 📌
node라는 클래스를 따로 만들어서 index 값과 부모 값을 넣어준다. 그 후 union과 find 함수를 통해서 알고리즘을 진행하도록 만들었다.

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new node[n+1];

        for(int i=1; i<=n; i++) {
            arr[i] = new node(i, i);
        }

        for(int i=1; i<=n; i++) {
            System.out.println(arr[i].index + "  " + arr[i].value);
        }

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

            if(c ==  0) {
                union(a, b);
            }
            else if(c == 1) {
                int find_a = find(a);
                int find_b = find(b);

                if(find_a == find_b) {
                    System.out.println("YES");
                }
                else {
                    System.out.println("NO");
                }
            }
        }
    }
    private static void union(int index_a, int index_b) {
        arr[index_b].value = arr[index_a].value;
    }
    private static int find(int index) {
        return arr[index].value;
    }
}
class node {
    int index;
    int value;

    public node(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

📌 재도전 📌
위 문제는 find 함수를 재귀함수로 만들지 않고 너무 단순하게 만들었다는 게 문제이다. 그래서 재귀함수로 만들었다.

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new node[n+1];

        for(int i=1; i<=n; i++) {
            arr[i] = new node(i, i);
        }

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

            if(c ==  0) {
                union(a, b);
            }
            else if(c == 1) {
                if(checkSame(a, b)) {
                    System.out.println("YES");
                }
                else {
                    System.out.println("NO");
                }
            }
        }
    }
    private static void union(int index_a, int index_b) {
        index_a = find(index_a);
        index_b = find(index_b);
        if(index_a != index_b) {
            arr[index_b].value = index_a;
        }
    }
    private static int find(int index) {
        if(index == arr[index].value)
            return index;
        else
            return arr[index].value = find(arr[index].value);
    }

    public static boolean checkSame(int index_a, int index_b) {
        index_a = find(index_a);
        index_b = find(index_b);
        if(index_a == index_b) {
            return true;
        } else {
            return false;
        }
    }
}
class node {
    int index;
    int value;

    public node(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

📌 재도전 📌
배열의 0번째를 초기화를 하지 않아서 NullPointer 에러가 발생한 것 같다. 그래서 배열 초기화 부분을 수정해서 다시 제출했다.

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new node[n+1];

        for(int i=0; i<=n; i++) {
            arr[i] = new node(i, i);
        }

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

            if(q ==  0) {
                union(a, b);
            }
            else if(q == 1) {
                if(checkSame(a, b)) {
                    System.out.println("YES");
                }
                else {
                    System.out.println("NO");
                }
            }
        }
    }
    private static void union(int index_a, int index_b) {
        index_a = find(index_a);
        index_b = find(index_b);
        if(index_a != index_b) {
            arr[index_b].value = index_a;
        }
    }
    private static int find(int index) {
        if(index == arr[index].value)
            return index;
        else
            return arr[index].value = find(arr[index].value);
    }

    private static boolean checkSame(int index_a, int index_b) {
        index_a = find(index_a);
        index_b = find(index_b);
        if(index_a == index_b) {
            return true;
        } else {
            return false;
        }
    }
}
class node {
    int index;
    int value;

    public node(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1717