Algorithm 공부 #19 - 트리의 특성과 트라이

 

Algorithm 공부 #19 - 트리

 

 

트리(tree)

  ● 노드와 에지로 연결된 그래프

  ● 순환(cycle)구조를 가지고 있고, 1개의 루트 노드가 존재

  ● 루트 노드를 제외한 모든 노드들은 단 1개의 부모 노드를 가짐

  ● 트리의 부분 트리(서브 트리)역시 트리의 특징을 따름

  ● 트리의 구성 요소

      1. 루트 노드 : 트리에서 가장 최상단에 위치하는 노드

      2. 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 위치하는 노드

      3. 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 위치하는 노드

      4. 리프 노드 : 자식 노드가 없는 가장 하위에 위치하는 노드

      5. 노드 : 데이터의 index와 value를 표현하는 요소

      6. 에지 : 노드와 노드의 연결 관계를 나타내는 선

      7. 서브 트리 : 전체 트리에 속한 부분 트리

    ● 트리의 탐색은 주로 dfs로 탐색

 

 

백준 11725번 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 ● 인접 리스트로 그래프 표현/ 양방향으로 입력 받기

 ● 방문 여부 체크 배열과 부모 노드 출력 배열 크기 초기화 및 내부 값들 초기화

 ● 루트 노드가 1번이므로 dfs를 1번부터 돌려주기

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>>tree;
vector<bool>visit;
vector<int>parent;
void dfs(int number);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	tree.resize(N + 1);
	for (int i = 0; i < N-1; i++) { // 인접 리스트 입력 완료
		int node1, node2;
		cin >> node1 >> node2;
		tree[node1].push_back(node2);
		tree[node2].push_back(node1);
	}

	visit.resize(N + 1); // 방문 배열 부모 배열 모두 초기화
	parent.resize(N + 1);
	fill(visit.begin(), visit.end(), false);
	fill(parent.begin(), parent.end(), 0);

	dfs(1);

	for (int i = 2; i <= N; i++)
		cout << parent[i] << '\n';
}
void dfs(int number) {
	visit[number] = true;

	for (int i : tree[number]) {
		if (visit[i] == false) {
			parent[i] = number;
			dfs(i);
		}
	}
}

 

 

 

백준 1068번 트리

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

1068번: 트리

 ● 인접 리스트로 그래프 표현/ 양방향으로 입력 받기

 ● 방문 여부 체크 배열과 부모 노드 출력 배열 크기 초기화 및 내부 값들 초기화

 ● 루트 노드가 제거노드와 같다면 0을 출력, 그게 아니라면 루트 노드부터 dfs탐색

 ● dfs함수에서 방문하는 노드가 제거노드라면 탐색하지 않기

 ● dfs함수에서 자식 노드의 개수를 세주면서 자식 노드의 개수가 0이라면 리프노드 개수 증가

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>>tree;
vector<bool>visit;
vector<int>answer;
vector<int>temp;
void dfs(int number);
int N;
int node;
int ans = 0;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	tree.resize(N);
	visit.resize(N);
	answer.resize(N);

	fill(visit.begin(), visit.end(), false);
	fill(answer.begin(), answer.end(), -2);
	int root;
	for (int i = 0; i < N; i++) { //인접 리스트 구현
		int a;
		cin >> a;
		if (a == -1)
			root = i;
		else {
			tree[i].push_back(a);
			tree[a].push_back(i);
		}
	}
	cin >> node;
	if (node == root) {
		cout << 0;
		return 0;
	}
	else {
		dfs(root); // 루트 노드부터 dfs탐색
		cout << ans;
	}
}
void dfs(int number) { // 탐색 완료
	visit[number] = true;
	int cnode = 0;

	for (int i : tree[number]) {
		if (!visit[i]&&i!=node) {
			answer[i] = number;
			cnode++;
			dfs(i);
		}
	}
	if (cnode == 0)
		ans += 1;
}

 

 

 

트라이(trie)

  ● 문자열 검색을 빨리 할 수 있도록 설계한 트리 형태의 자료구조

  ● 루트 노드는 항상 빈 문자열을 뜻하는 공백으로 채우고 그 밑에 노드들은 각 단어의 시작알파벳(26개)

  ● 단어를 삽입할 때 검색 노드가 공백 상태이면 신규 노드를 생성하고, 그게 아니라면 계속 이동

 

 

백준 14425번 문자열 집합

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

class Node 	//트라이 자료 구조 저장용 클래스
{
public:
    Node* next[26];
    bool isEnd;
    Node() : isEnd(false) {
        fill(next, next + 26, nullptr);
    }

    ~Node() {
        for (auto& child : next)
            delete child;
    }

    void insert(const char* key) {		// 문자열 삽입 함수
        if (*key == 0)
            isEnd = true;
        else {
            int next_index = *key - 'a';
            if (next[next_index] == nullptr)
                next[next_index] = new Node();

            next[next_index]->insert(key + 1);
        }
    }

    Node* find(const char* key) {		// 문자열 찾기 함수
        if (*key == 0)
            return this;

        int next_index = *key - 'a';
        if (next[next_index] == nullptr)
            return nullptr;

        return next[next_index]->find(key + 1);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    Node* root = new Node();

    while (n > 0) {  	// 트라이 자료구조 구축하기
        char text[501];
        cin >> text;
        root->insert(text);
        n--;
    }

    int count = 0;
    while (m > 0) {  	// 트라이 자료구조 검색하기
        char text[501];
        cin >> text;
        Node* result = root->find(text);
        if (result && result->isEnd) {
            count++; 	// S집합에 포함되는 문자열
        }
        m--;
    }
    cout << count << "\n";
}