패스트캠퍼스 챌린지 29일차

트리 (Tree)

- 그래프의 특수한 형태

 - V + E + 특성

  

 특성 1. 

  - 모두가 연결되어 있는 그래프

  - 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능

 

 특정 2.

  - 사이클이 존재하지 않음

 

 특성 3.

  - 정점 개수 v = 간선 개수 e + 1

 

특성중 2가지를 만족하면 트리로 문제 풀이

 

Rooted Tree란?

 1. Node

 2. Root

 3. Depth

 4. Parent, Child, Ancestor(조상),Sibling(형제, 같은 부모를 갖는 관계)

 5. Leaf Node (자식이 없는 노드)

 

<키워드>

 - 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우

 - 마을과 마을 사이를 직접 잇는 N-1 개의 길이 있으며, 모든 마을은 연결되어있다 (1,3 만족)

 

트리는 인접 리스트로 구현한다.

 -> 공간 복잡도 이슈 때문에

 

트리문제의 핵심

 - 정점 & 간선에 대한 정확한 정의

 - 트리의 요소와 문제의 요구 사항 매치

 

 

트리의 부모 찾기 (BOJ 11725)

 - 루트 없는 트리가 주어질때, 트리의 루트를 1이라고 정했을 떄, 각 노드의 부모를 구하는 문제

  

구현 방법

 1. 인전 리스트로 저장

 2. ROOT 말고는 아무것도 정답을 구하지 못한 상태로 시작

 3. 정점 X가 Parent를 안다면, 자신의 자식 Children을 찾을 수 있다.

  3-1 ) 연결된 것들 중 Parent를 제외한 모든것들

 4. Root 부터 차례대로 문제를 해결해보자

 => 탐색 알고리즘 : BFS or DFS 하지만 DFS 를 사용하자

 

    static int n;
    static ArrayList<Integer>[] adj;
    static int[] parent;
    
    // dfs(x, par) := 정점 x 의 부모가 par 였고, x의 children들을 찾아주는 함수
    static void dfs(int x, int par) {
        for (int y : adj[x]) {
            if (y == par) continue;
            parent[y] = x;
            dfs(y, x);
        }
    }

    static void pro() {
        // 1 번 정점이 ROOT 이므로, 여기서 시작해서 Tree의 구조를 파악하자.
        dfs(1, -1);

        // 정답 출력하기
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append('\n');
        }
        System.out.println(sb);
    }

 

 

트리 **

 접근 - 정답의 최대치

  단말 노드의 개수 <= 전체 정점의 개수 < = N , Integer 범위 안에 들어온다

 

 Subtree

 - X와 그 모든 자손들을 포함하는 트리를 만든다, X가 새로운 Root가 되며 새로운 트리가 만들어 지는것이다.

 

 큰문제와 작은문제

 큰문제 : 트리 안에 있는 단말 노드의 개수

 작은 문제 : Root의 자식 노드들의 subtree안에 있는 단말노드의 개수

 

 
    static int n, root, erased;
    static ArrayList<Integer>[] child;
    static int[] leaf;

    // dfs(x, par) := 정점 x 의 부모가 par 였고, Subtree(x) 의 leaf 개수를 세주는 함수
    static void dfs(int x, int par) {
        if (child[x].isEmpty())
            leaf[x]++;
        for (int y : child[x]) {
            if (y == par) continue;
            dfs(y, x);
            leaf[x] += leaf[y];
        }
    }

    static void pro() {
        // erased와 그의 부모 사이의 연결을 끊어주기
        for (int i=0;i<n;i++){
            if (child[i].contains(erased)){
                child[i].remove(child[i].indexOf(erased));
            }
        }
        
        // erased 가 root 인 예외 처리하기
        if (root != erased) dfs(root, -1);
        
        // 정답 출력하기
        System.out.println(leaf[root]);
    }

 

 

29일차 인증

 

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]