백준 1717: 집합의 표현 (java)

2024년 새해 목표!! 1일1백준!!

 

근데 계절학기 들으면서 우주공강 때 할게 없어가지고.. 미리 시작해봤다.

언어는 나중에 백엔드를 지원할 생각이라 자바를 선택했다.

 

이번 1717번 문제는 자료구조 수업 때 한번 풀어봤던 문제인데,

그때는 전과 직후라 잘 모르는 상태에서 교수님 코드를 따라 치기만 했다.

 

이번에 다시 풀어보니까 훨씬 이해도 잘 되고 골드 문제임에도 금방 풀 수 있었다.

 

---

 

알고리즘

그래프: Union-Find

 

체감 난이도

★ ★ ★ ☆ ☆

 

다시 풀 수 있는가?

NO

 

---

 

1. 재귀함수

 

x의 부모를 찾는 과정 중, 재귀함수를 써야한다는 생각을 못했다.

재귀함수로 (x == parent[x]) 할 때까지 타고타고 올라가야한다!

 

    public int findParent(int x) {
        if (x == parent[x]) {
            return x;
        }

        return parent[x] = findParent(parent[x]);
    }

 

2. 삼항연산자

 

조건식 ? 반환값1 : 반환값2

 

sb.append(hasSameParent(a, b) ? "YES" : "NO");

 

전체 코드 ▼

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1717 {
    static int[] parent;

    public void setParent(int n) {
        parent = new int[n+1];

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

    // b의 부모를 a의 부모로 치환
    public void union(int a, int b) {
        int u = findParent(a);
        int v = findParent(b);

        if (u != v) {
            if (u < v) {
                parent[v] = u;
            }
            else {
                parent[u] = v;
            }
        }
    }

    public int findParent(int x) {
        if (x == parent[x]) {
            return x;
        }

        return parent[x] = findParent(parent[x]);
    }

    public boolean hasSameParent(int a, int b) {
        int u = findParent(a);
        int v = findParent(b);

        return (u == v);
    }

    public void solution() throws Exception {
        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());

        setParent(n);

        for (int i = 0; i < m; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int unionOrAsk = Integer.parseInt(st2.nextToken());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());

            StringBuilder sb = new StringBuilder();

            // union
            if (unionOrAsk == 0) {
                union(a, b);
            }
            // find
            else if (unionOrAsk == 1) {
                sb.append(hasSameParent(a, b) ? "YES" : "NO");
                System.out.println(sb);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new BOJ1717().solution();
    }
}