[백준/BOJ] 백준 25601번 : 자바의 형변환

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

25601번: 자바의 형변환

 

각 클래스의 부모 클래스에 대한 정보를 저장해 놓고, 형 변환이 가능한지 확인하는 두 클래스(check1, check2)가 주어질때, 각 클래스가 부모일 때와 자식일 때 상황을 모두 확인해 보며, 자식위치에서 부모위치로 올라가면서 두 클래스가 같은 줄에 있는지 확인하여 형변환이 가능한지 확인했다.

 

코드

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

int n;
map<string, int> name_id; //(클래스 이름, 클래스 id)
int name_id_cnt = 0;

vector<int> parent(100005, -1);

bool check(int here_id, int find_id) {

	//find 클래스까지 도달할 수 있을때
	if (here_id == find_id) {
		return true;
	}

	//루트 클래스까지 왔는데 못찾을때
	if (parent[here_id] == -1) {
		return false;
	}

	return check(parent[here_id], find_id);
}

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

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		string a, b;
		cin >> a >> b;

		if (name_id.count(a) == 0) {
			name_id.insert(make_pair(a, name_id_cnt));
			name_id_cnt++;
		}

		if (name_id.count(b) == 0) {
			name_id.insert(make_pair(b, name_id_cnt));
			name_id_cnt++;
		}

		int a_id = name_id[a];
		int b_id = name_id[b];

		parent[a_id] = b_id;
	}

	string check1, check2;

	cin >> check1 >> check2;

	int check1_id = name_id[check1];
	int check2_id = name_id[check2];

	if (check(check1_id, check2_id) || check(check2_id, check1_id)) {
		cout << 1 << "\n";
	}
	else {
		cout << 0 << "\n";
	}

	return 0;
}