섹션 3. 코딩테스트 [실전편] - 09. 트리 - (1) 트리, 트라이

섹션 3. 코딩테스트 [실전편] - 09. 트리

🏓 선형 vs 비선형 자료구조

1) 선형 자료구조 : 현재 자료와 뒤 자료가 1:1 관계

2) 비선형 자료구조 : 현재 자료와 뒤 자료가 1:n 관계

---

⬛ 09. 트리

⬛ 09-1. 트리

• 사이클 X. 1개의 루트 노드만 가지고 있는 원소들 간의 1대 n 관계를 갖는 비선형 자료구조
• 상위 원소 → 하위 원소로 확장되는 구조
• 사이클X, 간선 N-1개 연결 그래프

🟧 트리의 구성요소

루트 노드 : 트리 가장 상위의 노드
부모 노드 : 두 노드 사이 관계에서 상위 노드
자식 노드 : 두 노드 사이 관계에서 하위 노드
리프 (단말) 노드 : 트리 가장 하위의 말단에서 자식 없는 노드
서브 트리 : 전체 트리에 속해있는 작은 하위 트리
각각의 노드는 자식 노드의 수만큼 서브 트리를 가질 수 있다.

---

⬛ 백준 11725번. 트리의 부모 찾기 - DFS 문풀

💚 문제 접근 방식

• 루트는 고정 1이다.
• DFS(1) 호출해서 매번 현 정점의 인접 정점이 방문 전인 상태일 경우에 한해서 쭉 깊이 탐색을 시도한다.
• 그리고 answer[현재] = 다음 식으로 구성해주면 직전 값 = 부모가 된다.
• 2번~N번까지 차례로 answer값 출력해주면 된다.

💚 제출 코드

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 11725번. 트리의 부모 찾기 
 * @author MYLG
 *
 */
public class Main {
	static int N;
	static ArrayList<ArrayList<Integer>> tree;
	static boolean[] visited;
	static int[] answer;
	//DFS
	static void DFS(int v) {
		
		for(int nx : tree.get(v)) {
			if(!visited[nx]) {
				visited[nx] = true;
				answer[nx] = v;//nx의 부모를 직전으로 세팅해줌
				DFS(nx);
				visited[nx] = false;
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		visited = new boolean[N+1];
		answer = new int[N+1];
		
		tree = new ArrayList<>();
		//초기화
		for(int i=0; i<=N; i++) {
			tree.add(new ArrayList<>());
		}
		
		//데이터 입력 
		for(int i=0; i<N-1; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			//양방향 간선 추가 
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		
		
		visited[1] = true;
		//무조건 1로 싲가 
		DFS(1);
		
		for(int i=2; i<=N; i++) {
			System.out.println(answer[i]);
		}	
	}
}

---

🟦 백준 1068번. 트리의 리프노드 개수 구하기

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

풀이

• 결국 제거하는 노드가 나왔을 때 탐색을 종료하는 아이디어를 사용하면 해당 노드에 대해서는 더 깊이 탐색을 하지 않는다.
• DFS or BFS 로 탐색을 할 때 어쨋든 해당 노드에 대한 자식 노드들을 카운팅해야 한다. 대신 카운팅 시 방문X 제거대상 노드 아닐 경우에만 자식노드를 카운팅한다.
• 자식노드를 모두 카운팅하고 나왔는데도 여전히 자식노드의 개수 =0 일 경우 단말노드가 된다. 이때 answer 값을 ++ 처리하면 최종 정답이 된다.

package to_0707_4;

import java.util.ArrayList;
import java.util.Scanner;

/*1068번. 트리 */
public class Main {
	static int N;
	static boolean visited[];
	static int answer= 0;//단말노드 개수 
	static int deleteNode;//삭제 노드 
	static ArrayList<Integer> [] graph;
	//dfs
	static void dfs(int v) {
		visited[v] = true;
		int child=0;//각 v에 대한 자식 카운팅용 
		
		for(int nx : graph[v]) { //인접 정점 뽑아와서 
			if(!visited[nx] && nx != deleteNode) { //삭제노드이면 깊이탐색 중지하여 끊는 효과 담기 
				//여기서 각 노드의 자식 노드 개수 처리 
				child++; //자식 ++ 처리 
				dfs(nx);//더 깊이 탐색 
			}
		}
		
		//탈출 후에도 여전히 자식 =0인 경우 단말 노드이므로 답++
		if(child ==0 ) {
			answer++;
		}	
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		visited = new boolean[N];
		graph = new ArrayList[N];
		for(int i=0; i<N; i++) {
			graph[i] = new ArrayList<Integer>();
		
		}
		int root = 0;
		//입력 데이터 저장하기 
		for(int i=0; i<N; i++) {
			//a는 부모노드이고 i에 저장할거임 
			int x = kb.nextInt();
			if(x != -1) {
				//양방향 
				graph[i].add(x);
				graph[x].add(i);
			}else {
				//부모 세팅 
				root = i;
			}
		}
		
		//삭제노드 입력받기 
		deleteNode = kb.nextInt();
		
		if(deleteNode == root) {//루트 노드가 삭제노드일 경우 
			System.out.println(0);//단말노드는 0개
		}else {
			dfs(root);//호출
			System.out.println(answer);//다남ㄹ 노드 개수 출력 
		}
	}
}

---

⬛ 09-2. 트라이

🟦 트라이 (trie)

• 문자열 검색을 빠르게 실행할 수 있도록 설계된 트리 형태의 자료구조
• 단어들을 사전 형태로 생성한 뒤, 트리의 부모 자식 관계 이용하여 검색을 수행한다.

🟧 트라이의 특징

• 1) N진 트리
  • 문자 종류에 따라 N이 결정된다. ex) 알파벳 = 26개 문자
• 2) 루트 노드는 항상 공백 노드

🟧 트라이 수행 방식

1. 루트 노드는 공백 유지
2. 루트 노드부터 각 문자 검색하는데

• (1) 삽입 시, 검색 노드가 공백 상태이면 신규 노드 생성
• (2) 아니면 이동하는 원리