[백준]5021 왕위 계승

문제소개

---

5021왕위 계승 문제는 dfs로 tree형태의 그래프를 형성하는 문제입니다. tree형태를 만든 다음 주어진 계승자를 계산하면 풀수 있는 문제입니다.

 

문제풀이

---

먼저 노드 구조체를 만들겠습니다.

트리의 노드 형태는 다음과 같습니다.

struct node {
	string _name;
	vector<node> _child;

	node(){}
	node(string name) {
		this->_name = name;
	}
};

각 트리의 노드를 정의했으니 트리를 만들겠습니다.

트리는 dfs로 구성할 것이며 제일 먼저 주어진 유토피아의 왕부터 시작합니다.

void dfs(node& parent) {
	int j = 0;
	for (int i = 0; i < N; i++) {
		if (lines[i][1] == parent._name || lines[i][2] == parent._name) {
			parent._child.push_back(node(lines[i][0]));
			dfs(parent._child[j]); //자식 객체를 부모로 dfs 돌리기
			j += 1;
		}
	}
}

예시에서 주어진 데이터를 사용하겠습니다.

왕 (edwardi node) 를 dfs 함수의 parent 인자로 전달합니다.

그리고 주어진 가족 정보를 통해 전달 받은 parent._name 값이 부모인지 아닌지 판단합니다.

부모이면 전달받은 parent 객체의 _child Array에 추가하고 child 객체를 부모하여 dfs 인자로 전달합니다.

이렇게 하면  간단하게 tree 형태가 완성됩니다.

double sol(string target, node &start, int depth) {
	double ret = 0;

	if (start._name == target) return ret += pow(0.5, depth);
	else {
		for (int i = 0; i < start._child.size(); i++) {
			ret += sol(target, start._child[i], depth + 1);
		}
	}
	return ret;
}

이제 계승자들의 계승점수를 매깁니다.

주어진 계승자들을 target으로 하여 왕 (edwardi node)를 시작으로 탐색합니다.

이때도 dfs를 통해 계승점수를 계산합니다.

 

결론은 tree 형태를 dfs로 만들고, 계승점수도 dfs로 계산하면 되는 문제입니당.