백준 13237 c++ : 트리, 재귀

재귀 구조 변경점

int dfs(vector<int>& node, int current, int layer) {
	if (node[current] == -1) {
		return layer;
	}
	else {
		return dfs(node, node[current], layer + 1);
	}
}

재귀함수에서 return dfs(node, node[current], layer + 1);와 dfs(node, node[current], layer + 1);의 차이로 인해 첫 시도에서 메모리 초과가 발생했다.
dfs(node, node[current], layer + 1);는 기존 함수의 메모리는 해제되지 않은 채 새로운 dfs 함수가 계속 호출되기에 금방 메모리 초과가 발생한다.
가능하다면 return을 통해 기존 함수의 메모리를 해제해 재귀함수에서도 메모리 누수를 막아야 한다.

그러나 재귀는 어쨌건 효율적으로 떨어진다. 반복문 사용도 연습해 본다.

#include <iostream>
#include <vector>

using namespace std;

void input_data(int* n, vector<int>& node) {
	int i, parent;

	cin >> *n;
	node.resize(*n + 1);
	for (i = 1; i <= *n; i++) {
		cin >> parent;
		node[i] = parent;
	}

	return;
}

int dfs(vector<int>& node, int current, int layer) {
	if (node[current] == -1) {
		return layer;
	}
	else {
		return dfs(node, node[current], layer + 1);
	}
}

void find_answer(int n, vector<int>& node) {
	int i;

	for (i = 1; i <= n; i++) {
		int layer = 0;

		cout << dfs(node, i, layer) << "\n";
	}

	return;
}

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

	int n;
	vector<int> node;

	input_data(&n, node);
	find_answer(n, node);

	return 0;
}