[220815][Tany][인프런](9-6) 친구인가

[juni8453]

📌 문제

• 문제

⭐️ 아이디어

• 글로 읽으면 당연히 3과 8은 친구가 아니라는게 눈에 보이는데 이걸 어떻게 그리디 알고리즘으로 풀이할까 ?
• 강의에 Union-Find 가 적혀있어서 구글링을 해봤는데, 블로그 글로만 읽으니 이해가 잘 안되서 인강을 듣고 이해해보려고 했다.

🤔 고민한 내용

• 그리디 알고리즘은 미래를 걱정하지 않고 현재 최선의 선택을 했을 때의 최종 해가 최적의 해라는 기대를 갖는 알고리즘이다.
• 1까지의 수, 거스름돈 요런 문제는 그리디인줄 알겠는데 이런 문제는 어째서 그리디 알고리즘인지 잘 모르겠다.
• 찾아보니, 그리디 알고리즘은 따로 풀이방법이 정해져있지 않기 때문에 많이 풀어보고 감을 익히는게 최고인 것 같다.

💪 새롭게 배운 내용

• 서로소 집합을 만들고 판단할 수 있게하는 Union-Find 자료구조 구현에 대해 알게되었다.

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

• Union-Find 자료구조라는 것을 알지 못해서..ㅋㅋ

✅ 본인 풀이

package study.section9;

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

import java.util.StringTokenizer;

public class Section0906 {
    static int[] unf;

    // 배열에서 소속된 집합을 찾아주는 메서드
    static int Find(int v) {
        if (v == unf[v]) {
            return unf[v];
        } else {
            return unf[v] = Find(unf[v]);
        }
    }

    // 합치는 메서드
    static void Union(int a, int b) {
        int fa = Find(a);
        int fb = Find(b);
        if (fa != fb) unf[fa] = fb;
    }

    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());
        unf = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            unf[i] = i;
        }

        for (int i = 1; i <= m; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            Union(a, b);
        }

        StringTokenizer st3 = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st3.nextToken());
        int b = Integer.parseInt(st3.nextToken());

        int fa = Find(a);
        int fb = Find(b);

        if (fa == fb) System.out.println("YES");
        else System.out.println("NO");
    }
}

참고한 자료

• 이것이 취업을 위한 코딩 테스트다 by 나동빈