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

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

 

 

 

#문제 간단 정리

그래프 탐색을 하면 된다

 

#문제 해결 방법

 

dfs로 풀었는데

 

트리의 부모만 확인해 주면 되니까 이렇게 복잡하게 풀 필요는 없어보인다..

그래서 실버1인듯하다

 

#전체 코드

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

map<string, vector<string>> node;
map<string, bool> dfsCheck;
int result;

void dfs(string start, string target) {

    if (start == target) {
        result = 1;
        return;
    }



    for (auto a : node[start]) {
        if (!dfsCheck[a]) {
            dfsCheck[start] = true;
            dfs(a, target);
            dfsCheck[start] = false;
        }
    }

    
}

int main() {
    int n;
    cin >> n;

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

        dfsCheck[s1] = false;
        dfsCheck[s2] = false;

        node[s1].push_back(s2);
    }

    string a1, a2;
    cin >> a1 >> a2;
    result = 0;

    dfs(a1, a2);
    dfs(a2, a1);
    
    cout << result << '\n';

    return 0;
}