[JAVA] 백준 트리 뿌수기2

 

 

이전글

https://fladi.tistory.com/405

[JAVA] 백준 트리 뿌수기1

 

 

트리 부수기 2탄이다! 아직 트리부분이 많이 부족해서 얼른 성장하고싶다

 

 

 

20364 부동산 다툼 - 실버1

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

20364번: 부동산 다툼

• 꽉꽉마을이다 ㅎㅎ
• 이진트리인 걸 티낸다
• 각각 자기 땅을 찾아가면서 visit를 확인하면 될듯

 

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

        st.nextToken();
        int duckCnt = Integer.parseInt(st.nextToken());

        Map<Integer, Boolean> map = new HashMap<>();

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<duckCnt; i++) {
            int num = Integer.parseInt(br.readLine());
            int tmp = num;
            int first = 1;
            while (tmp != 1) {
                if (map.get(tmp) != null) {
                    first = tmp;
                }
                tmp /= 2;
            }

            if (first == 1) {
                map.put(num, true);
                sb.append("0\n");
            } else {
                sb.append(first + "\n");
            }
        }

        System.out.print(sb);
    }
}

• 입력받으면서 땅을 살 수 있는지 확인함
• 왼쪽자식인지 오른쪽자식인지 모르겠어서 리프에서 루트까지 거슬러 올라가면서 처음 만나는 땅을 찾음
  • 왼쪽으로 가는지 오른쪽으로 가는지 확인할 수 있는 방법이 있으면 좋겠다.. 있는지 찾아봐야지
• 가는 길에 점유지가 없으면 자신이 산 땅을 HashMap에 체크하고 0출력
• 가는 길에 점유지가 있으면 해당 땅을 출력

 

 

다른 기발한 풀이가 없는지 찾아봤다. 

1. 리프노드에서 루트로 가고, boolean 배열로 visit를 저장하는 풀이
   • 대부분이 이 방식으로 푼듯
   • https://dhbang.tistory.com/32

 

좌우를 확인하는 방법은 리프에서 루트로 거슬로올라가는 방법밖에 없나보다. 

 

 

 

 

1068 트리 - 골드5

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

1068번: 트리

• 그냥 전체트리 리프노드 - 서브트리의 리프노드 + a 를 하면 될듯
• a는 없애는 노드의 부모가 자식이 있다면 0이고, 자식이 없다면 1이다.
• 이번에도 트리 구성하는 것에 애먹을 것 같다

 

public class Main {
    static ArrayList<Integer>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        int root = 0;
        int[] parents = new int[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if (parent == -1) {
                root = i;
                continue;
            }
            arr[parent].add(i);

            parents[i] = parent;
        }

        int removeNum = Integer.parseInt(br.readLine());

        int globalLeafCount = findLeaf(root);
        int localLeafCount = findLeaf(removeNum);

        int result = globalLeafCount - localLeafCount;

        int p = parents[removeNum];
        if (arr[p].size() == 1) {
            result ++;
        }

        System.out.print(result);
    }

    private static int findLeaf(int node) {
        int count = 0;
        List<Integer> children = arr[node];
        if (children.size() == 0) {
            count++;
            return count;
        }

        for (Integer child: children) {
            count += findLeaf(child);
        }

        return count;
    }
}

• 트리 구성이 익숙하지 않아 다익스트라 냄새나게 트리를 구성했다
  • parent에 자식들을 줄줄이 매다는 방법을 사용했다
• 루트부터 재귀호출로 리프노드를 찾았고
• 지울 노드부터 재귀호출로 리프노드를 찾았다
• parents 배열을 쓰고싶지 않았지만 나의 직속부모를 빠르게 찾을 수 있는 방법이라 결국 썼다.. 다른 더 좋은 풀이가 있을 것 같아서 찾아봐야겠다

 

 

다른풀이

1. 삭제한 노드를 표시하고, 삭제되지 않은 트리 중 리프노드를 카운트하는 방법
   • parents[] 배열만 이용하였고
   • 트리에서 삭제된 노드를 표시하여 해당 노드는 카운트하지 않도록 설계하셨다
   • 삭제된 노드를 찾기위해서 모든 parent를 돌면서 해당 parent가 삭제된 노드를 parent로 가지는지 확인한다
   • 그리고 카운트할 때는 parent를 돌면서 매개변수를 부모로 가지는 자식을 카운팅한 후 개수가 0이면 리프노드로 판별한다.
   • 시간복잡도가 클 것 같지만 노드의 개수가 50개 이하이므로 충분히 가능한 풀이같다.
   • https://moonsbeen.tistory.com/229
2. 양방향 연결하는 그래프로 푸는 방법
   • visit를 체크하며 연결노드를 탐색하면서 리프노드를 체크한다
   • 삭제된 노드에서는 그냥 끊어버려서 리프노드로 체크안한다 (우와!)
   • 나는 이 방법이 꽤 마음에든다. 단반향으로 하되, 삭제된 노드를 끊어버리는 아이디어가 좋은 것 같다
   • https://usedto-wonderwhy.tistory.com/175

 

 

 

 

1240 노드사이의 거리 - 골드5

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

1240번: 노드사이의 거리

• dfs하면 될 것 같은데?

 

class Node {
    int end;
    int distance;

    public Node(int end, int distance) {
        this.end = end;
        this.distance = distance;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nodeCnt = Integer.parseInt(st.nextToken());
        int pairCnt = Integer.parseInt(st.nextToken());

        visit = new boolean[nodeCnt];
        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, distance));
            arr[b].add(new Node(a, distance));
        }

        StringBuilder sb=  new StringBuilder();
        for (int i =0; i<pairCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            visit[a] = true;
            sb.append(find(a, b, 0) + "\n");
            visit[a] = false;
        }

        System.out.print(sb);
    }

    private static int find(int start, int target, int distance) {
        if (start == target) {
            return distance;
        }

        int result = 0;
        for (Node adj: arr[start]) {
            if (!visit[adj.end]) {
                visit[adj.end] = true;
                result = find(adj.end, target, distance + adj.distance);
                visit[adj.end] = false;
                if (result != 0) {
                    break;
                }
            }
        }

        return result;
    }
}

• 특별할 것 없고 그냥 dfs만 잘하면 된다
• 찾아내면 거리계산한 거 반환하면 됨
• 트리라서 한 노드에서 다른 노드로 가는 길이 하나밖에 없음. 쉽다

 

 

 

 

5639 이진 검색 트리 - 골드5

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

5639번: 이진 검색 트리

• 전위순회한 결과로 트리를 만든 후, 후위순회를 하면 될 것 같다
• 전위순회는 중왼오이므로, 맨 처음값이 루트임을 알 수 있다. 이걸 이용해서 트리를 만들고 후위순회하면 될듯
• (while로 계속 입력받는 부분은 어떻게 처리해야할지 몰라서 다른 풀이를 참고했다)

 

class Node {
    int num;
    Node left;
    Node right;

    public Node(int num, Node left, Node right) {
        this.num = num;
        this.left = left;
        this.right = right;
    }

    public void insert(int tmp) {
        if (tmp > num) {
            if (right != null) {
                right.insert(tmp);
            } else {
                right = new Node(tmp, null, null);
            }
        } else {
            if (left != null) {
                left.insert(tmp);
            } else {
                left = new Node(tmp, null, null);
            }
        }
    }
}

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

        int rootNum = Integer.parseInt(br.readLine());
        Node root = new Node(rootNum, null, null);

        while (true) {
            String input = br.readLine();
            if (input == null || input.equals("")) {
                break;
            }

            int num = Integer.parseInt(input);

            root.insert(num);
        }

        postOrder(root);
    }

    private static void postOrder(Node node) {
        if (node.left != null) {
            postOrder(node.left);
        }
        if (node.right != null) {
            postOrder(node.right);
        }
        System.out.println(node.num);
    }
}

• 처음엔 배열에 저장하려고 했는데, 트리가 비대칭일 경우 배열을 너무 크게잡아야할 것 같아 그냥 root에 계속 매달아줬다.
• 트리를 구성한 뒤에는 어렵지 않게 후위순회를 할 수 있었다.

 

루트에 주렁주렁 매다는 방법이 일반적인지 확인하고 싶어 다른 풀이도 찾아봤다.

 

 

다른풀이

1. 나와 비슷한 풀이(이게 거의 바이블 수준인듯)
   
   • https://ksb-dev.tistory.com/250
   • https://rudyprogramming.tistory.com/132
   • https://girawhale.tistory.com/59
2. 이진탐색처럼 푸는 풀이
   • 굉장히 참신하다 (이전에도 본 적 있는듯)
   • 일단 List에 다 넣은다음 계속 반을 쪼개면서 postOrder를 호출한다
   • 전위순회의 규칙을 잘 이용한 것 같다. 다음에 규칙찾고 블로그 포스팅해야지
   • https://jainn.tistory.com/349

 

 

 

 

15681 트리와 쿼리 - 골드5

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

15681번: 트리와 쿼리

• 트리를 구성하고, 자신의 자손의 개수를 카운트해서 저장해두면 될 것 같다
• 문제에 설명이 자세하게 나와있어서 참고하면 큰 도움이 될듯. 좋은문제다!!

 

public class Main {
    static Map<Integer, Integer> childrenCnt = new HashMap<>();
    static Map<Integer, List<Integer>> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        int nodeCnt = Integer.parseInt(st.nextToken());
        int rootNum = Integer.parseInt(st.nextToken());
        int queryNum = Integer.parseInt(st.nextToken());

        map = new HashMap<>();

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

            List<Integer> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a, list);

            List<Integer> list2 = map.getOrDefault(b, new ArrayList<>());
            list2.add(a);
            map.put(b, list2);
        }

        makeTree(rootNum, rootNum);

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<queryNum; i++) {
            int num = Integer.parseInt(br.readLine());
            sb.append(childrenCnt.get(num)+1);
            sb.append("\n");
        }

        System.out.print(sb);
    }

    private static int makeTree(int node, int parent) {
        int cnt = 0;
        for (Integer adj: map.get(node)) {
            if (parent != adj) {
                int tmpChildrenCnt = makeTree(adj, node);
                cnt += (tmpChildrenCnt + 1);
            }
        }

        childrenCnt.put(node, cnt);

        return cnt;
    }
}

• 일단 노드간의 관계를 map에 저장한다(연결리스트의 배열로 해도 상관없을듯)
• 이걸로 트리를 구성하면서 각 노드의 자손의 수를 childrenCnt 라는 map에 각각 저장해준다
  • 재귀적으로 자손들을 호출하며 각 자손의 개수를 카운트하고 리턴하는 식으로 만들었다
  • 문제의 참고자료를 많이 활용함(parent를 매개변수로 넣는 등)
• 이후 각각에 맞는 자손의 수를 print한다. 자손의 수만 저장했기 때문에 +1을 해줘야한다.

 

 

 

 

17073 나무 위의 빗물 - 골드5

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

17073번: 나무 위의 빗물

• 노드들의 평균값을 계산하면서 리프노드까지 내려가고, 리프노드의 평균을 구하려고 했다
• 시간초과가 엄청나서 구글링해봤는데, 내가 너무 어렵게 생각했던 것 같다
  • 참고자료: https://loosie.tistory.com/523
• 빗물은 리프노드에 균등하게 분배될 것이므로, 평균값은 빗물양/리프노드 개수로만 구하면 됐다 
• 수학적으로 생각할껄..

 

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

        int nodeCnt = Integer.parseInt(st.nextToken());
        int water = Integer.parseInt(st.nextToken());

        ArrayList<Integer>[] arr = new ArrayList[nodeCnt];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < nodeCnt - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            arr[a].add(b);
            arr[b].add(a);
        }

        int leafCnt = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].size() == 1) {
                leafCnt++;
            }
        }

        System.out.println(String.format("%.10f", (double)water/leafCnt));
    }
}

 

 

 

 

24230 트리 색칠하기 - 골드5

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

24230번: 트리 색칠하기

• 루트노드부터 내려가며 색이 바뀌는 부분이 있다면 result를 추가하면 될듯
• 어렵지 않은 문제다
• 15681 문제를 푼 후에 풀이가 많이 깔끔해졌다. 트리만드려고 애쓰지도 않아도 되고 너무 좋다.. 
  (글쓴이의 트리인생은 15681 문제를 풀기 전과 후로 나뉜다)

 

public class Main {
    static ArrayList<Integer>[] arr;
    static int[] colors;
    static int result= 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        StringTokenizer st= new StringTokenizer(br.readLine());

        colors = new int[nodeCnt];
        arr = new ArrayList[nodeCnt];
        for (int i=0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt; i++) {
            colors[i] = Integer.parseInt(st.nextToken());
        }

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

            arr[a].add(b);
            arr[b].add(a);
        }

        scanTree(0, 0, 0);

        System.out.println(result);
    }

    private static void scanTree(int node, int parent, int parentColor) {
        if (colors[node] != parentColor) {
            result++;
        }

        for (Integer adj: arr[node]) {
            if (parent != adj) {
                scanTree(adj, node, colors[node]);
            }
        }
    }
}

 

 

 

 

1967 트리의 지름 - 골드4

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

1967번: 트리의 지름

• 트리라고 생각할수록 더 안풀리는 문제다
• 애초에 부모자식 관계를 친절하게 제시하는 것부터 이상하긴했다
• 그냥 리프노드부터 다른 리프노드까지 dfs로 가장 긴 거리를 찾는 게 맞는 방법이다. 그냥 dfs라고 생각하는 게 좋을듯

 

class Node {
    int end;
    int value;

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

public class Main {
    static ArrayList<Node>[] arr;
    static boolean[] visit;
    static int tmpMax = 0;

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

        arr = new ArrayList[nodeCnt];
        visit = new boolean[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<nodeCnt-1; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken())-1;
            int child = Integer.parseInt(st.nextToken())-1;
            int value = Integer.parseInt(st.nextToken());

            arr[parent].add(new Node(child, value));
            arr[child].add(new Node(parent, value));
        }

        int max = 0;
        for (int i =0; i<arr.length; i++) {
            if (arr[i].size() == 1) {
                tmpMax = 0;
                dfs(i, 0);

                if (tmpMax > max) {
                    max = tmpMax;
                }
            }
        }

        System.out.println(max);
    }

    private static void dfs(int node, int sum) {
        visit[node] = true;

        boolean isEnd = true;

        for (Node adj: arr[node]) {
            if (!visit[adj.end]) {
                visit[adj.end] = true;
                dfs(adj.end, sum+adj.value);
                visit[adj.end] = false;
                isEnd = false;
            }
        }

        visit[node] = false;

        if (isEnd) {
            if (sum > tmpMax) {
                tmpMax = sum;
            }
        }
    }
}

• 그냥 dfs임

 

 

 

3584 가장 가까운 공통 조상 - 골드4

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

3584번: 가장 가까운 공통 조상

• 루트에서 내려가면서 두 노드를 찾는지 확인하면 될듯

 

public class Main {
    static ArrayList<Integer>[] children;
    static int parent = 0;

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

        for (int tc=0; tc<tcCnt; tc++) {
            int nodeCnt = Integer.parseInt(br.readLine());
            parent = 0;
            children = new ArrayList[nodeCnt];
            boolean[] isNotRoot = new boolean[nodeCnt];
            for (int i=0; i<children.length; i++) {
                children[i] = new ArrayList<>();
            }
            for (int i =0; i<nodeCnt-1; i++) {
                st = new StringTokenizer(br.readLine());
                int parent = Integer.parseInt(st.nextToken())-1;
                int child = Integer.parseInt(st.nextToken())-1;
                children[parent].add(child);
                isNotRoot[child] = true;
            }

            int root = 0;
            for (int i =0; i<isNotRoot.length; i++) {
                if (!isNotRoot[i]) {
                    root = i;
                    break;
                }
            }

            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            find(root, a, b);

            System.out.println(parent+1);
        }
    }

    private static boolean[] find(int node, int a, int b) {
        boolean[] isFind = new boolean[2];
        if (node == a) {
            isFind[0] = true;
        }
        if (node == b) {
            isFind[1] = true;
        }

        for (Integer adj: children[node]) {
            if (adj == a) {
                isFind[0] = true;
            } else if (adj == b) {
                isFind[1] = true;
            }

            if (isFind[0] && isFind[1])
                break;

            boolean[] tmpFind = find(adj, a, b);
            if (tmpFind[0]) {
                isFind[0] = true;
            } else if (tmpFind[1]) {
                isFind[1] = true;
            }
        }

        if (isFind[0] && isFind[1] && parent == 0) {
            parent = node;
        }

        return isFind;
    }

}

• 루트부터 내려가면서 a와 b를 동시에 찾은 첫 번째 노드를 result에 저장하는 방법으로 해결하였다.
• 루트를 찾기위해 isNotRoot배열을 만들어 false인 애가 루트라고 지정해줬다
• 분명 나보다 좋은 풀이가 많을 거라고 생각하여 더 찾아봤다

 

 

다른풀이

1. 노드 하나에서 루트까지 쭉 타고 올라감 -> 체크하면서 올라간다/ 나머지 노드에서 루트까지 타고올라가면서 체크된 곳 확인, 처음 만나는 체크표시 = 답
   • 이게 가장 정석풀이인 것 같다. 이걸 왜 생각못했지?
   • 참고: https://dhbang.tistory.com/34
2. LCA풀이방법이라고 한다. 최소 공통조상이라고 하는데, 노드전체 수가 1만개면 충분히 풀이가 가능하다고 한다.
   • 루트노드를 찾아낸 후,
   • 해당 노드까지 탐색하여 높이값, 부모노드를 저장하고
   • 높이를 맞춰준 후, 부모노드가 일치할 때까지 찾아낸다고 한다
   • 높이를 맞추는 게 꽤 참신한 것 같다! 한 번 봐두면 좋을ㄷ스
   • 참고: https://loosie.tistory.com/466
3. 루트노드가 0을 부모로 가지게 하고, 각 노드에서 부모까지 타고올라가며 stack에 넣음
   • 이후 stack에서 하나씩 꺼내보면서 비교
   • 참고: https://skdltm117.tistory.com/51

역시나 참신한 풀이들이 많다. 참고해두면 나중에 도움이 될 것 같다

 

 

 

 

4803 트리 - 골드4

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

4803번: 트리

• 그래프가 트리인지 확인해야한다. 
• 사이클여부를 판별하는 Unionfind를 사용해도 되겠지만, 나는 경로가 유일하다는 특징을 사용하려고 한다
• 한 점에서 연결된 그래프를 따라내려가면서 visit를 체크하고, 만약 자식 중 이미 visit된 게 있으면 트리가 아닌 걸로 판별하겠다

 

public class Main {
    static ArrayList<Integer>[] arr;
    static boolean[] visit;
    static boolean isTree = true;

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

        StringBuilder sb = new StringBuilder();
        int caseNum = 1;

        while (true) {
            st = new StringTokenizer(br.readLine());
            int nodeCnt = Integer.parseInt(st.nextToken());
            int lineCnt = Integer.parseInt(st.nextToken());

            if (nodeCnt == 0 && lineCnt == 0) {
                break;
            }

            visit = new boolean[nodeCnt];
            arr = new ArrayList[nodeCnt];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            String result = "No trees.";

            for (int i = 0; i < lineCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken()) - 1;
                int b = Integer.parseInt(st.nextToken()) - 1;
                arr[a].add(b);
                arr[b].add(a);
            }

            int count = 0;
            for (int i = 0; i < nodeCnt; i++) {
                isTree = true;
                if (!visit[i]) {
                    dfs(i, i);
                    if (isTree) {
                        count++;
                    }
                }
            }

            if (count == 1) {
                result = "There is one tree.";
            } else if (count > 1) {
                result = "A forest of " + count +" trees.";
            }

            sb.append("Case " + caseNum + ": " + result);
            sb.append("\n");
            caseNum++;
        }
        System.out.print(sb);
    }

    private static void dfs(int node, int prev) {
        visit[node] = true;

        for (Integer adj: arr[node]) {
            if (prev != adj) {
                if (!visit[adj]) {
                    dfs(adj, node);
                } else {
                    isTree = false;
                }
            }
        }
    }
}

• visit되지 않은 노드의 이전노드를 체크하면서 dfs를 돌린다
• dfs를 하는 도중에 이미 지나간 길을 발견하면 사이클이 있는거다 -> 트리가 아님
• dfs를 다 해도 지나간 길을 발견하지 못하면 트리임 -> 트리개수 count++

 

 

더 좋은 풀이가 많을 것 같아 또 서치해봤다

1. 일반적인 dfs접근
   • dfs로 간선 수를 세서 (정점-1) 이면 트리로 판별, 아니면 트리가 아닌걸로 판별한다
   • 참신한 풀이다! 재밌음
   • 참고: https://dhbang.tistory.com/25
2. 방문하지 않은 노드에 대해 bfs수행, 에지 개수가 (정점-1)인지 확인하여 판별
   • bfs로 푸는 풀이도 있다. 재밌음
   • 참고: https://ksb-dev.tistory.com/113
3. dfs를 수행하며 사이클 판별(나와 비슷한 풀이)
   • 참고: https://velog.io/@solser12/%EB%B0%B1%EC%A4%80-4803-%ED%8A%B8%EB%A6%AC-JAVA
4. 노드개수를 세는 방법과 UnionFind 사용
   • 두 방법 모두로 푸셨다
   • 간선에 대해 Unionfind 연산 중, 두 노드의 부모가 같으면 사이클이 발생한 것이라고 함
   • 참고: https://velog.io/@minseojo/%EB%B0%B1%EC%A4%80-4803.-%ED%8A%B8%EB%A6%AC-Java

 

 

 

 

union find 알고리즘을 복습해야겠다