Minimum Time to Collect All Apples in a Tree

ㅋㅋ·2023년 1월 11일
0

알고리즘-leetcode

목록 보기
90/135

노드의 개수 n, 노드 간의 엣지들이 담긴 2차원 정수형 벡터,

인덱스 기준 노드가 사과를 가지고 있는지의 유무가 담긴 불리언 벡터를 받는다.

노드에서 인접한 노드(노드 간의 엣지가 존재하는)로 이동하는데 1초가 걸릴 때,

0번 노드에서 시작하여 모든 사과를 모으고 0번 노드로 돌아올 때 걸리는 시간을 구하는 문제

문제에서 한가지 놓치기 쉬운 건 노드의 자식 노드 개수와 부모 노드 개수에 제한이 없다는 것

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        
        vector<vector<int>> graph(n);

        int length = edges.size();
        for (int i = 0; i < length; i++)
        {
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
        }

        vector<bool> visited(n);
        visited[0] = true;

        return SearchDFS(0, graph, visited, hasApple);
    }

    int SearchDFS(int index, vector<vector<int>> &table, vector<bool> &visited, vector<bool>& hasApple)
    {
        int result{0};
        for (int i = 0; i < table[index].size(); i++)
        {
            if (visited[table[index][i]])
            {
                continue;
            }

            visited[table[index][i]] = true;
            result += SearchDFS(table[index][i], table, visited, hasApple);
            visited[table[index][i]] = false;
        }

        if (index != 0)
        {
            if (hasApple[index])
            {
                result += 2;
            }
            else if (0 < result)
            {
                result += 2;
            }
        }
        
        return result;
    }
};

0개의 댓글