(백준 1068번 트리 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Tree 1

오늘은 자료구조 Tree에 대해 배워보았씀당ㅎㅎ

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220788265724&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

트리(Tree) (수정: 2018-11-22)

 

백준 1068번

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

1068번: 트리

#include <iostream>
//★ algorithm : remove와 erase header
#include <algorithm> 
#include <vector>
#include <queue>
using namespace std;

int N, node;
int root; 

class Tree {
public: 
	int N; 
	vector<int> p;
	vector<vector<int>> c;

	Tree(int N) : N(N) {
		p.resize(N, -1);
		c.resize(N);
	}

	void findLeaf(int node) {
		// node의 parent -2로 만들기
		queue<int> Q;
		Q.push(node);
		int pnode = p[node];
		// ★ node의 부모 c[p[node]]에서 node 삭제해주기
		if(p[node] != -1) c[p[node]].erase(remove(c[p[node]].begin(), c[p[node]].end(), node), c[p[node]].end());

		while (!Q.empty()){
			int r = Q.front();
			p[r] = -2;
			Q.pop();
			for (int child : c[r]) {
				Q.push(child);
			}
		}

		// leaf 갯수 세기
		int cnt = 0;

		queue<int> q;
		q.push(root);

		// ★ 이게 없으면 반례가 생김
		// 5
		// 1 2 3 4 -1
		// 3
		// 답 : 1 오답 : 0
		if (p[root] != -2 && c[root].empty()) {
			if (root != node) {
				cout << "1"; 
				return;
			}
		}
		
		while (!q.empty()) {
			int i = q.front();
			q.pop();
			if (p[i] != -2 && !c[i].empty()) {
				//	cout << "i : " << i << endl;
					// ★ leaf 인지 확인해주기
				for (int j : c[i]) {
					if (!c[j].empty()) {
						q.push(j);
						continue;
					}
					cnt++;
				}
			}
		}

		
		cout << cnt;
	}
};
int main() {
	cin >> N;
	Tree t(N);
	for (int i = 0; i < N; i++) {
		cin >> t.p[i];
		if (t.p[i] == -1) {
			root = i;
			continue;
		}
		t.c[t.p[i]].push_back(i);
	}

	cin >> node;
	t.findLeaf(node);

	return 0;

}

꽤나 유용했던 반례

 

참고로 내가 너무 요상복잡하게 풀어서 잘 푸신 분의 풀이를 가져왔다.

혹시,, 함부로 가져오면 안되는거면 알려주세요!! 

너무 맘에 들어 가져왔습니다..!!

// 출처 ㅣ scsc3313님 풀이

#include <cstdio>
int N, M, root, parent[50], t;
int cntleaf(int now)
{
    if (now == M)
        return 0;
    int ans = 0;
    for (int i = 0; i < N; ++i)
        if (parent[i] == now)
            ans += cntleaf(i);
    return ans ? ans : 1;
}
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &t);
        if (t == -1)
            root = i;
        parent[i] = t;
    }
    scanf("%d", &M);
    printf("%d", cntleaf(root));
}