[Algorithm] 8주차 스터디 - Graph & Tree (백준 1991, 11725, 1068, 15681)

A - 백준 1991번 트리 순회

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

1991번: 트리 순회

* 문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

* 코드

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

int N;
char P, L, R;
int parent[26][2];

void preOrder(char root) { // 전위순회
    if (root == '.') return;
    else {
        cout << root;
        preOrder(parent[root - 'A'][0]);
        preOrder(parent[root - 'A'][1]);
    }
}

void inOrder(char root) { // 중위순회
    if (root == '.') return;
    else {
        inOrder(parent[root - 'A'][0]);
        cout << root;
        inOrder(parent[root - 'A'][1]);
    }
}

void postOrder(char root) { // 후위순회
    if (root == '.') return;
    else  {
        postOrder(parent[root - 'A'][0]);
        postOrder(parent[root - 'A'][1]);
        cout << root;
    }
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P >> L >> R;
		parent[P - 'A'][0] = L;
		parent[P - 'A'][1] = R;
	}

    preOrder('A');
    cout << '\n';
    inOrder('A'); 
    cout << '\n';
    postOrder('A');
}

* 문제 풀이
전위 순회는 해당 노드에 방문하자마자 출력하고, 왼쪽 자식이 존재하면 왼쪽자식을 방문한다.
위의 절차를 반복하고 왼쪽 자식이 없다면 이제 오른쪽 자식을 방문한다.
오른쪽 자식을 방문했을 때도 출력 -> 왼쪽 자식 확인 -> 오른쪽 자식 확인하는 순서로 진행된다.
중위 순회는 왼쪽 자식 확인 -> 출력 -> 오른쪽 자식 확인
후위 순회는 왼쪽 자식 확인 -> 오른쪽 자식 확인 -> 출력
같은 방식으로 진행된다.

 

B - 백준 11725번 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

* 문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
[Input] 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
[Output] 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

* 코드

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

vector<vector<int>> tree(100001);
vector<bool> visited(100001, false);
vector<int> parent(100001, 0);

void search(int start){
    for(int i = 0; i < tree[start].size(); i++){
        int now = tree[start][i];
        if(!visited[now]){
            visited[now] = true;
            parent[now] = start;
            search(now);
        }
    }
}

int main(void){
    int N;
    cin >> N;

    for(int i = 0; i < N - 1; i++){
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    search(1); // 루트부터 시작

    for(int i = 2; i <= N; i++){
        cout << parent[i] << "\n";
    }
}

* 문제 풀이
루트 노드인 1부터 Search를 하면서 이전에 방문을 한 적이 있으면 visited[now] = true로 바꿔준다.
이렇게 탐색을 진행하게 될 경우, 어떤 노드에서 다음으로 방문할 노드들은 자식 노드임이 성립하게 되는 것을 알 수 있다.

 

C - 백준 1068번 트리

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

1068번: 트리

* 문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.
[Input] 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
[Output] 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

* 코드

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

vector<vector<int>> tree;
int erase, answer;

void search(int node){
    int child = 0;
    int size = tree[node].size();
    for(int i = 0; i < size; i++){
        int x = tree[node][i];
        if(x == erase) continue;
        search(x); child++;
    }
    if(!child) answer++;
}

int main(){
	int N, parent, root;
	cin >> N;
    tree = vector<vector<int> >(N);
    for(int i = 0; i < N; i++){
		cin >> parent;
        if(parent == -1){
            root = i;
            continue;
        }
        tree[parent].push_back(i);
    }
	cin >> erase;
    if(root == erase) cout << "0";
    else{
        search(root);
		cout << answer;
    }
}

* 문제 풀이
우선적으로 트리를 만들어주고, 삭제할 노드를 받은 후에 
루트에서부터 탐색해 나가면서 
삭제된 노드를 제외한 자식 노드가 0개인 노드의 개수를 세주면 된다.

D - 백준 15681번 트리와 쿼리
https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

* 문제
간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.
정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.
[Input] 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105). 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V). 이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다. 이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N) 입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.
[Output] Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력한다.

 

* 코드

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

int ans[101010];
vector<int> tree[101010];

int search(int now, int prev){
	ans[now] = 1;
	for(auto next: tree[now]){
		if(prev == next) continue;
		ans[now] += search(next, now);
	}
	return ans[now];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, R, Q; 
	cin >> N >> R >> Q;

	for(int i=0; i<N-1; i++){
		int a, b; cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	search(R, 0);

	while(Q--){
		int t; 
		cin >> t;
		cout << ans[t] << "\n";
	}
}

* 문제 풀이
트리를 돌면서 서브 트리의 노드 수를 size에 저장해준다. 이때 말단 노드를 만나면 사이즈를 return한다.