[백준/BOJ] 백준 17306번 : 전쟁 중의 삶

https://www.acmicpc.net/problem/17306

17306번: 전쟁 중의 삶

 

군부대가 있는 도시의 숫자를 2진수 비트로 표현한 뒤, 해당 2진수 비트를 트라이로 표현해서 만들어지는 트라이의 노드의 개수를 구하고 트라이에서 군부대 도시 노드들의 최소 공통 조상(LCA) 노드 위에 있는 노드들(위험하지 않은 도시)의 개수를 빼서 위험한 도시의 개수를 구하는 방법으로 문제를 해결했다.

 

다음 이미지는 군부대가 있는 도시의 번호가 8,9 일 때 예시이다.

 

군부대가 있는 도시의 번호가 8,9 일 때 예시

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
using namespace std;

//군부대가 있는 도시의 숫자를 2진수 비트로 표현해서, 해당 숫자를 트라이에 넣어 만들어지는 트라이의 노드의 개수를 구하고 최소 공통 조상 노드 위에 있는 노드의 개수를 빼는 방법으로 문제를 해결

struct node {
	bool finish;
	long long children_cnt;
	node* children[2];
};

long long n;
node* root;

node* NewNode() {

	node* ret = new node();

	ret->finish = false;
	ret->children_cnt = 0;
	for (int i = 0; i < 2; i++) {
		ret->children[i] = NULL;
	}

	return ret;
}

void InputNode(node*& here, string& input, long long index) {

	if (input.size() == index) {
		here->finish = true;
		return;
	}

	here->children_cnt++;

	if (here->children[stoi(input.substr(index, 1))] != NULL) {
		InputNode(here->children[stoi(input.substr(index, 1))], input, index + 1);
	}

	else {
		here->children[stoi(input.substr(index, 1))] = NewNode();
		InputNode(here->children[stoi(input.substr(index, 1))], input, index + 1);
	}

}

//앞에 0을 자른다
string CutZero(string input) {
	long long index = input.find("1");
	return input.substr(index);
}

//만들어진 노드의 개수를 센다
long long CountNode(node*& here) {

	if (here->children_cnt == 0) {
		return 0;
	}

	long long ret = 0;

	if (here->children[0] != NULL) {
		ret += (1 + CountNode(here->children[0]));
	}

	if (here->children[1] != NULL) {
		ret += (1 + CountNode(here->children[1]));
	}

	return ret;
}

//루트노드에서 부터 최소 공통 조상 정점까지 도달하는데 거치는 정점의 개수를 센다
//즉 위험하지 않은 도시들의 개수를 센다
long long CountErase(node*& here) {

	long long ret;

	if (here == root) {
		ret = 0;
	}

	else {
		ret = 1;
	}

	long long here_children_cnt = here->children_cnt;
	long long there_children_cnt;

	if (here->children[0] != NULL) {
		there_children_cnt = here->children[0]->children_cnt;

		if (here_children_cnt != there_children_cnt) { //here부분이 최소 공통 조상일때
			ret = 0;
		}

		else {
			ret += CountErase(here->children[0]);
		}
	}

	else {
		there_children_cnt = here->children[1]->children_cnt;

		if (here_children_cnt != there_children_cnt) { //here부분이 최소 공통 조상일때
			ret = 0;
		}

		else {
			ret += CountErase(here->children[1]);
		}
	}

	return ret;
}

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

	root = NewNode();

	cin >> n;
	for (int i = 0; i < n; i++) {
		long long input;
		cin >> input;

		//bitset을 이용하여 십진수를 2진수 비트로 표현
		string bit_input = CutZero(bitset<51>(input).to_string());

		//트라이에 해당 2진수 문자열을 넣는다
		InputNode(root, bit_input, 0);
	}

	long long total_node_cnt = CountNode(root);
	long long erase_node_cnt = CountErase(root);

	cout << total_node_cnt - erase_node_cnt << "\n";

	return 0;
}