C++ / 백준 / 9489 / 사촌

문제

 

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

9489번: 사촌

문제풀이

 

주어진 조건을 통해 트리를 구성하고 노드의 번호 K의 부모노드, 조상 노드(부모의 부모)를 구해 K의 형제 노드를 제외한 손자 노드를 구하면 된다.

숫자는 연속으로 주어지지 않으므로 (쓰지 않는 숫자가 있음) map을 이용하여 트리를 구성했다.

 

		unordered_map<int, vector<int>>tree;
		unordered_map<int, int>parent_map;

총 두 개의 map을 구성했다.

tree는 부모노드 / 자식노드들로 구성하는 map,

parent_map은 자식노드 / 부모노드로 구성했다.

 

문제의 조건을 보면 집합(위의 vector)은 연속된 수이고, 연속된 수가 아닐 경우 새 집합의 수이다.

새 집합은 자식이 없는 노드 중 가장 작은 수를 가지는 노드의 자식의 집합이 된다.

 

		int parent_idx(-1);
		for (int idx = 1; idx < nodes.size(); ++idx) {
			if (nodes[idx - 1] + 1 < nodes[idx]) {
				++parent_idx;				
			}
			int parent_node = nodes[parent_idx];
			tree[parent_node].push_back(nodes[idx]);
			parent_map[nodes[idx]] = parent_node;
		}

코드의 구성은 입력을 먼저 받는다.

그리고 parent_idx라는 변수를 만들어 입력받은 노드를 가리키게 한다.

parent_idx번째 노드는 부모의 노드를 의미한다.

 

만약 연속된 수가 아니라면 ++parent_idx를 하여 다음 노드로 이동한다.

parent_node는 nodes의 parent_idx번째 노드가 된다.

tree [부모 노드]에 현재 노드를 push_back 한다.

parent_map은 자식노드 / 부모노드로 구성된 map이므로 현재 자식노드의 값을 부모노드로 저장한다.

 

이 반복문이 종료되면 트리가 완성이 된다.

 

		int ancestor_node(0), answer(0);
		ancestor_node = parent_map[parent_map[target]];
		
		for (int idx = 0; idx < tree[ancestor_node].size(); ++idx) {
			int child_node = tree[ancestor_node][idx];			
			if (child_node == parent_map[target]) continue;			
			answer += tree[child_node].size();
		}

 

그다음은 사촌을 찾는 반복문이다.

사촌은 부모가 같으면 안 되고, 조상이 같아야 한다.

두 번의 parent_map을 통해 조상의 노드를 찾는다.

 

반복문을 통해 조상의 노드의 자식 노드를 구한다.

만약 조상의 노드의 자식 노드가 찾는 K노드의 부모라면 해당 노드의 자식들은 형제가 되므로 continue를 통해 넘긴다.

그 외의 경우는 모두 사촌 노드들 이므로 tree[child_node].size() 만큼 값을 누적하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

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

	int max_node(0), target(0);

	while (1) {
		cin >> max_node >> target;
		if (max_node == 0 && target == 0) break;
		
		vector<int>nodes(max_node, 0);
		unordered_map<int, vector<int>>tree;
		unordered_map<int, int>parent_map;

		for (int idx = 0; idx < max_node; ++idx) {
			cin >> nodes[idx];
		}
		
		int parent_idx(-1);
		for (int idx = 1; idx < nodes.size(); ++idx) {
			if (nodes[idx - 1] + 1 < nodes[idx]) {
				++parent_idx;				
			}
			int parent_node = nodes[parent_idx];
			tree[parent_node].push_back(nodes[idx]);
			parent_map[nodes[idx]] = parent_node;
		}

		int ancestor_node(0), answer(0);
		ancestor_node = parent_map[parent_map[target]];
		
		for (int idx = 0; idx < tree[ancestor_node].size(); ++idx) {
			int child_node = tree[ancestor_node][idx];			
			if (child_node == parent_map[target]) continue;			
			answer += tree[child_node].size();
		}
		cout << answer << '\n';
	}
}