• 관련 문제
  : 1325번. 효율적인 해킹.

241118 부족한 부분

• 반환값이 있는 재귀의 경우, 중요한 부분이 있다.

• 아래의 입력을 넣으면 2가 나와야 하는데, 1이 출력된다.
  

• 반환값이 적용되는 재귀를 만들경우, 이런식으로 하게되면, 원치 않는 반환값이 이전에 호출한 재귀에 적용되는 경우가 있다.

결론

: 반환값이 있고, 누적되는 재귀의 경우, 지금 반환되는 재귀가 이전 재귀에 영향을 줄수 있따는 생각을 해야 한다.

지금의 경우, 38~39번 줄 처럼 처리하면 안된다. -1을 부모로 하는 3번 노드의 경우, 1이 반환되어야 하는데, 0으로 반환되는 상황이 발생한다. ...

• 재귀재귀 누적되는 경우에 어떻게 해야 덮어써지지 않고 처리가 가능할까?? 를 생각해야 한다.

---

최근 풀이 241031

• 이거는 노드로는 전혀 풀수가 없다.
  1) 루트노드가 반드시 0번 정점이라는 것을 확정할 수 없다.
  2) 앞선 정점이 뒷번호 정점을 부모로 삼을 수 있따.

-> 지금까지 진행한 생각을 버리고, 빠르게
다른 방법을 생각해내야 한다.

// 자식노드를 기준으로 해서 parent 를 저장했다.
v[각 정점 번호] = parent 그런데 지금의 경우, 노드방식으로 못하기 때문에
// 다른 방법을 생각하자.

• 문제에서 말하는게 리프노드의 개수이다.
  그러면 v[부모의 정점] 에다가 자식노드의 정점을 push하는 방식으로 진행하면 되지 않을까???? 를 생각해야 한다.

그리고

• 끊어지는 부분은 erase 하지 말고, 스킵하면서 진행하면 될듯 하다.
  

1번째 풀이

• 리프노드는 대상으로 한 정점의 벡터 사이즈가 0인경우를 의미한다.
  그래서 이렇게 작성했다.
  -> 70퍼센트 올라가다가 틀림.
  

2번째 풀이

: 뭐가 잘못되었을까? 생각해보자.

• for문을 보면, deleteNum 한 값은 continue를 하게 된다.
  만약에 deleteNum에 1개의 정점이 있다고 한다면, 이 친구의 경우도 return 1 처리를 바로 해야 한다. 53번줄까지 내려가면 누적된다.
  그냥 바로 1 반환을 해야 하기 때문에 로직을 이렇게 변경하니까 100점 맞았다.
  

-> 아 까다롭다...

---

알아두었으면 좋았을 stl 알고리즘

1. find
   : find를 잘 사용했더라면 코드를 줄일 수 있었음.

• 

2. erase
   : erase 는 반드시 이터레이터가 들어가야 함.

올바른 전략

: 그냥 문제 그대로 erase 하는 것이 맞음.

부족한 점.

• 1. erase
• 2. 반드시 0번 노드가 루트노드인 것은 아님.

맞왜틀?

• 백트래킹으로 자식노드가 없을 경우에 카운팅을 반환하는 방법으로 접근해야 함.
• 하지만, 나는 void이고, 전역을 누적하는 방식으로 했음.
  -> 이럴 경우에 한줄로만 연결되어 있는 상태에서 중간을 제거해버리면
  0이 나옴.
  

첫번째 풀이

: 입력예제는 모두 맞았는데, 틀림...

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <map>
#include <cstring>
#include <queue>


// 1068 트리
// 13:41 ~ 14:04 밥 먹자.

// 14:26 ~ 

struct tree
{
	int parent;
	vector<int>child;
};

int res = 0;
int n;
int m;

void dfs(vector<tree>&v , int startNode)
{
	if (startNode == m)
		return;

	if (v[startNode].child.empty())
	{
		//cout << "해당 노드의 번호는 " << startNode << endl;
		++res; 
		return;
	}

	int childSize = v[startNode].child.size();
	
	for (int i = 0; i < childSize; ++i)
	{
		// m인 곳은 탐색 못하게 하는 것이 훨씩 나을 듯함?
		//if (v[startNode].child[i] == m)
			//continue;
		dfs(v, v[startNode].child[i]);

	}


}

void Erase(int index, vector<tree>&v)
{
	// 루트노드부터 시작해서 
	// 노드 찾아서 밑에 있는 것부터 제거 해나가는 방식으로 ? 

	int ssize = v[index].child.size();

	for (int i = 0; i < ssize; ++i)
	{
		if (v[index].child[i] == m - 1)
		{

			//v[index].child.pop_back();
		}

	}


}


int main()
{
	// 0 번 노드에서부터 n - 1번 노드까지 
	
	cin >> n;

	vector<tree>v(n);

	for (int i = 0; i < n; ++i)
	{
		int n;
		cin >> n;
		v[i].parent = n;

		if (n < 0)
			continue;
		v[n].child.push_back(i);
	
	}

	//int realNodeCnt = 0;
	//for (int i = 0; i < v.size(); ++i)
	//{
	//	int ssize = v[i].child.size();
	//
	//	cout << i << "번 노드의 부모는 " << v[i].parent << endl;
	//	cout << i << "번 노드의 자식들은 " << endl;
	//	
	//	for (int j = 0; j < ssize; ++j)
	//	{
	//		cout << v[i].child[j] << " ";
	//	}
	//	cout << endl;
	//
	//}

	
	cin >> m;
	dfs(v, 0);
	cout << res;
	


}