백준 11725 트리의 부모 찾기

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
class TreeNode {
public:
	int data;
	vector<TreeNode*> connections;
	int connectionSize = 0;
	TreeNode() {
		data = 0;
	}
	TreeNode(int data) : data(data) {}
};

class Tree {
public:
	TreeNode head;
	int size;
	Tree(TreeNode head, int size) : head(head), size(size) {}
};
int main() {
	int size;
	scanf("%d", &size);
	int* parentArr = new int[size + 1];
	vector<TreeNode*> treenodeVector;

	treenodeVector.push_back(new TreeNode(0));
	for (int i = 1; i <= size; i++) {
		treenodeVector.push_back(new TreeNode(i));
		parentArr[i] = 0;
	}

	for (int i = 0; i < size - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		TreeNode* ANode = treenodeVector[a];
		TreeNode* BNode = treenodeVector[b];
		ANode->connections.push_back(BNode);
		ANode->connectionSize++;
		BNode->connections.push_back(ANode);
		BNode->connectionSize++;
	}

	queue<int> bfsSearchQueue;
	bfsSearchQueue.push(1);
	while (!bfsSearchQueue.empty()) {
		int parent = bfsSearchQueue.front();
		bfsSearchQueue.pop();
		TreeNode* parentNode = treenodeVector[parent];
		for (int i = 0; i < parentNode->connectionSize; i++) {
			int son = parentNode->connections[i]->data;
			if (son != parentArr[parent]) {
				parentArr[son] = parent;
				bfsSearchQueue.push(son);
			}
		}
	}
	for (int i = 2; i <= size; i++) {
		printf("%d\n", parentArr[i]);
	}
	return 0;
}

TreeNode는 자신과 연결된 다른 노드를 포인터 벡터로 가지고 있다.

ParentArr는 각 인덱스에 해당하는 노드의 부모를 저장하는 배열이다.

입력을 읽으면서 Node들을 초기화 하고,

1번 노드부터 Queue에 넣으면서 BFS를 시작한다.

BFS를 연산하다 보면, 부모 -> 자식 -> 부모 이런식으로 다시 부모로 거슬러 올라가는걸 방지하기 위해서

자식(son)이 본인의 부모(parentArr[parent])와 다를 경우에만 ParentArr를 갱신하고 Queue에 넣는다.

Queue가 빌때 까지 BFS를 연산 한 뒤, 계산되어 나오는 ParentArr의 값들이 정답.