Minimum Time to Collect All Apples in a Tree

1443. Minimum Time to Collect All Apples in a Tree

class Solution {
    vector<vector<int>> map;
    vector<bool> visit, has;
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        map = vector<vector<int>>(n);
        for (auto &e: edges) {
            map[e[0]].push_back(e[1]);
            map[e[1]].push_back(e[0]);
        }
        visit = vector<bool>(n, false);
        visit[0] = true;
        has = vector<bool>(hasApple);
        return find(0)<<1;
    }

    int find(int n) {
        int result = 0;
        for (auto nn: map[n]) {
            if (!visit[nn]) {
                visit[nn] = true;
                result += find(nn);
            }
        }
        if ((result || has[n]) && n) {
            ++result;
        }
        return result;
    }
};

matrix 로 index 를 vertex 로 가지는 tree 를 정의해 주고, 0 에서 부터 dfs.
현재 node 가 사과이거나 사과를 만난적이 있다면(리턴값이 1 이상) 결과에 1을 더해준다.(이동한 edge 의 수를 구함)
걸어서 왕복한다는 개념으로 구한 edge수 * 2 하면 답이 나온다.

Time: O(n)

• map 생성 n + 모든 vertex 순회 n

Space: O(n^2)

• matrix 로 tree 를 정의했으므로 n^2