트리 : Tree

트리 : Tree

• 그래프의 특수한 형태
• 트리 := 정점(V) + 간선(E) + 아래 특성 중 2개 이상 만족해야함
  1. 모든 정점이 연결되어있는 그래프
  2. 사이클이 존재하지 않음
  3. |V| = |E| + 1
• Rooted Tree
  • Node : Vertex
  • Root : 보통 가장 위에 그려지는 노드
  • Depth : 정점의 깊이, Root로부터 거리
  • Parent,Child,Ancestor,Sibling : 부모,자식,조상(→ 자신과 Root 사이의 관계) ,형제 (→ 같은 부모를 갖는 다른 정점들)
    
  • Leaf Node
• Keyword
  • 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다.
  • 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며 모든 마을은 연결되어있다.
    • 연결성, |E| = |V| - 1
  • 문제는 일반적인 그래프가 아니라 트리이다.(연결되어 있지만 사이클이 없는 그래프)
• 트리를 저장하는 방법
  • 인접 리스트 (Adjacency List)
  • 인접 리스트의 공간 복잡도는 O(E), 트리의 |E| = |V| - 1, 공간복잡도 이슈로 대부분 인접리스트 사용

---

BOJ_11725

트리의 루트를 1로 할 때, 각 노드의 부모는 어떻게 결정될까

• 알고리즘
  1. 인접 리스트로 저장하기
  2. Root부터 문제 풀기
  3. 정점 X가 parent를 안다면, 자신의 자식 child를 찾을 수있다.
  - 어떻게? 연결된 것들 중 parent를 제외한 모든 것들
  4. Root부터 차례로 문제를 해결해보자
  • 시간 복잡도, 공간 복잡도
    • DFS || BFS : 트리는 모두 인접 리스트를 이용하기 때문에 O(V+E)
    • 트리는 DFS로 매우 쉽게 구현 가능
  • 구현

       static void input(){
       	n = sc.nextInt();
       	adj = new ArrayList[N + 1];
       	parent = new int[N+1];
       	for(int i=1;i<=N;i++) adj[i] = new ArrayList<>();
       	for(int i=1;i<N;i++){
       		int x = sc.nextInt(), y = sc.nextInt();
       		adj[x].add(y);
       		adj[y].add(x);
       }
       // 정점 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(){
       	dfs(1,-1);
       	for(int i=2;i<=N;i++)
       		sb.append(parent[i]).append('\n');
       	System.out.println(sb);
       }
       

BOJ_1068:단말 노드

Rooted tree와 지울 노드가 주어진다. 노드 하나를 지우고 난 후 단말 노드(리프 노드)의 갯수를 세야한다.

• 단말 노드(Leaf Node)의 갯수
  • 정답의 최대치
    • 단말 노드의 개수 ≤ 전체 정점의 개수 ≤ N
  • 알고리즘

    1. 정점 제거

       정점이 사라진다? 정점과 이어진 간선들이 모두 사라진다 → 정점 X의 부모에서 X로 가는 간선 삭제 || 무시

    2. 트리의 단말 노드 개수 측정

       • DFS 탐색을 통해 단말 노드 개수 알기
       • Subtree 이용해 큰 문제의 정답을 작은 문제의 정답을 이용해 구하기
         • Root의 자식들을 Root로 하는 Subtree를 구성하여 각 Subtree 안에 있는 단말 노드의 개수 구하기
         • 트리 안에있는 단말 노드 개수<<큰 문제>> 를 Root의 자식 노드들의 subtree안에 있는 단말 노드의 개수 <<작은 문제>>의 정답을 이용해 구하자

    3. 단말 노드의 개수 세기

       • leaf[x] ; x를 root로 하는 subtree에 있는 단말 노드의 개수

       

       • x가 단말 노드인 경우 : leaf[0] = 1

       • x가 단말 노드가 아닌 경우 : x의 자식들에 대해 leaf를 먼저 계산하고, 그의 합

       • leaf[X] 계산하는법

         Root에서 DFS를 한다면, 노드 X에서 자식 Y에 대한 탐색을 끝나고 돌아오면 leaf[Y]가 계산되어 왔을테니 leaf[X]에 leaf[Y]를 누적해주면 된다.

         • DFS(X) : X의 subtree에 대해 leaf[X]를 계산해주는 함수
  • 구현

    static int N,root,erased;
    static ArrayList<Integer>[] child;
    static int[] leaf;
    
    static void input(){
    	N = sc.nextInt();
    	child = new ArrayList[N];
    	leaf = new int[N];
    	for(int i=0;i<N;i++) child[i] = new ArrayList<>();
    	for(int i=0;i<N;i++){
    		int par = sc.nextInt();
    		if(par == -1){ 
    			root = i; 
    			continue;
    		}
    		child[par].add(i);//자식 노드 기록
    	}
    	erased = sc.nextInt();
    }
    
    static void dfs(int x){
    	if(child[x].isEmpty()){
    			leaf[x] = 1;
    	}
    	for(int y : child[x]){
    		dfs(y);
    		leaf[x] += leaf[y];
    	}
    		
    }
    static void pro(){
    	// TODO : erased와 그의 부모 사이의 연결을 끊어주기
    	for(int i=0;i<N;i++){
    		if(child[i].contains(erased)){
    				child[i].remove(child[i].indexOf(erased));
    	}
    	// TODO : erased가 root인 예외 처리하기
    		if(root != erased) dfs(root);
    	// TODO : 정답 출력하기
    	System.out.println(leaf[root]);
    }