[백준 25601번] 자바의 형변환 (C++)

문제링크 : https://www.acmicpc.net/problem/25601

25601번: 자바의 형변환

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 

int N;
string A, B;
map<string, string>m;
bool flag;

void func(string s1, string s2)
{
    int T=N;
    while(T--)
    {
        if(s1==s2) //형변환 가능
        {
            flag=1;
            return;
        }
        s1=m[s1]; //연결된 값으로
    }
}

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

    cin >> N;
    for(int i=0; i<N-1; i++)
    {
        cin >> A >> B;
        m[A]=B; //A는 B의 자식
    }
    
    string s1, s2;
    cin >> s1 >> s2;

    func(s1, s2); //s1을 기준으로
    func(s2, s1); //s2를 기준으로

    cout << flag;
    return 0;
}

 

map을 활용하여 문자열의 부모관계를 연결해준다.

이후 부모 or 자식을 기준으로 그에 연결된 자식 or 부모를 확인하며 비교 대상 문자열과 같은지를 체크한다.

만약 같다면 형변환이 가능한 것이다.

형변환 가능 여부 확인을 위해 bool 변수 flag를 활용하였다.

 

양방향으로 체크를 해야하기에 (부모 -> 자식 + 자식 -> 부모) 연결된 값을 체크하는 함수 func에 대해 입력받는 문자열의 순서를 바꿔서 총 2번 함수를 돌려주었다.