[자료구조] 다중 트리(일반 트리)의 조상을 찾는 문제 (C++)

문제

---

N개의 노드로 구성된 트리가 입력으로 주어진다. 이때, 각 노드는 1번부터 N번까지 서로 다른 번호로 구분되며, 트리의 루트는 1이다. 노드 v의 조상(ancestor)은 노드 v부터 루트까지의 경로 상에 있는 노 드이다. 노드의 번호를 입력으로 받아, 해당 노드의 모든 조상들을 공백으로 구분하여 출력하는 프로그램을 작성하시오.

 

예제 입출력

예제 입력	예제 출력
10 4 1 2 1 3 1 4 2 5 3 6 3 7 6 8 6 9 6 10 4 8 5 9	1 6 3 1 2 1 6 3 1

---

 가장 처음으로 트리를 구현해봤던 건데 이제서야 올린다.

 딱히 어떤 순회나 탐색을 써야겠다고 생각하고 구현한건 아니고 그냥 순서대로 찾기...

 row index가 부모이고 column index가 자식이다.

 트리 벡터의 row, column을 순서대로 돌면서 조상을 찾으려는 노드를 찾고 그의 부모를 return, 그리고 부모의 부모를 또 return... 반복한다. root 노드에 도달하면 끝!

---

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//돌아가긴 하는데,,,

int parents(int v, vector<vector<int>> tr) {			//재귀로 풀어보자	
	for (int i = 1; i < tr.size(); i++) {
		if (tr[i].size() == 0) {
			continue;
		}
		if (v == 1) {
			return 1;
		}

		for (int j = 0; j < tr[i].size(); j++) {
			if (tr[i][j] == v) {
				cout << i << ' ';
				return parents(i, tr);
			}
		}
	}
}

int main() {
	int n, m, x, y, v;
	vector<vector<int>> tr;

	cin >> n >> m;
	tr.resize(n - 1);

	for (int i = 0; i < n - 1; i++) {
		cin >> x >> y;
		tr[x].push_back(y);
	}

	for (int i = 0; i < m; i++) {
		cin >> v;
		parents(v, tr);
		cout << endl;
	}
}