847. Shortest Path Visiting All Nodes

• 최소 경로를 구하는 문제로 BFS + memoization을 활용한다.

• 일반적인 BFS와는 다른 방식의 memoization을 사용해야 한다.
• 일반적인 BFS에서는 방문한 노드의 cost를 memoize할 때 key로 노드의 ID node ID를 사용했다면 여기서는 node ID 뿐만 아니라 해당 노드를 방문하기까지 방문했던 모든 노드의 목록visited node list(or state) 을 key로 해야 한다.
• 문제는 visited node list를 key로 표현하는 방법인데 전체 노드의 수가 12개 이하이므로 integer mask를 사용하여 표현하기로 한다.
• 결국 cost map의 key는 (node ID, mask)가 된다.

• 또한 기존과는 달리 시작 노드가 없으므로 모든 노드를 시작점으로 하여 BFS를 진행해야 한다.
• 이 문제의 경우 leaf node가 아닌 노드에서 시작할 경우 최소 경로 길이를 가질 수 없으므로 leaf node들의 목록만 뽑아서 시작점으로 하여 BFS를 진행하면 된다.
• 만일 leaf node가 없는 경우라면 graph가 cycle이라는 의미이므로 임의의 노드를 하나만 골라서 시작해도 무방하다.

• priority_queue를 사용하여 가장 cost가 낮은 (node ID, mask)를 기준으로 탐색을 진행한다.
• 인접 노드 next in graph[curr]마다
• 다음 노드next를 기준으로 다음 key를 정한다 next key = (next, currMask | 1 << next)
• cost[next key]가 cost[curr key] + 1보다 큰 경우 cost[next key]값을 cost[curr key] + 1로 갱신하고 priority_queue에 next key를 넣는다.

• 탐색이 종료되었다면 각 노드에 대해서 모든 노드를 방문한 상태key = (ID, allMask)의 cost 중 가장 작은 값을 결과로 돌려준다.

class Solution {
public:
    vector<int> getLeafNodes(vector<vector<int>>& graph) {
        vector<int> result;
        for (int i = 0; i < graph.size(); ++i) {
            if (graph[i].size() == 1) result.push_back(i);
        }
        return result;
    }

    int shortestPathLength(vector<vector<int>>& graph, int start, int allMask) {
        // (node ID, mask)
        using IDMask = pair<int, int>;
        map<IDMask, int> cost;
        // compare two key with cost
        auto compare = [&cost](IDMask& a, IDMask& b) {
            return cost[a] < cost[b];
        };
        // priority queue of IDMask
        using PQ = priority_queue<IDMask, vector<IDMask>, decltype(compare)>;
        PQ pq(compare);
        // start condition
        int startMask = 1 << start;
        cost[{start, startMask}] = 0;
        pq.emplace(start, startMask);
        int curr, currMask;
        while (!pq.empty()) {
            tie(curr, currMask) = pq.top();
            pq.pop();
            int currCost = cost[{curr, currMask}];
            // for each next node
            for (auto next : graph[curr]) {
                // mark visited to mask
                auto nextMask = currMask | 1 << next;
                // check next cost
                auto& nextCost = cost[{next, nextMask}];
                if (nextCost == 0 || currCost + 1 < nextCost) {
                    nextCost = currCost + 1;
                    // add next key if mask isn't all mask
                    if (nextMask != allMask)
                        pq.emplace(next, nextMask);
                }
            }
        }

        int result = -1;
        for (int i = 0; i < graph.size(); ++i) {
            // find minimum cost with all mask (all visited)
            auto itr = cost.find({i, allMask});
            if (itr == cost.end()) continue;
            auto currCost = itr->second;
            if (result == -1 || currCost < result)
                result = currCost;
        }
        return result;
    }

    int shortestPathLength(vector<vector<int>>& graph) {
        // get leaf nodes
        auto leafNodes = getLeafNodes(graph);
        // graph is cycle
        if (leafNodes.empty()) {
            leafNodes.push_back(0);
        }
        // get all mask
        int allMask = 0;
        for (int i = 0; i < graph.size(); ++i) {
            allMask |= 1 << i;
        }
        int result = -1;
        for (auto start : leafNodes) {
            // for each leaf node
            int length = shortestPathLength(graph, start, allMask);
            if (result == -1 || length < result)
                result = length;
        }
        return result;
    }
};