'2025/03/21'에 해당되는 글 1건

Leetcode Problem:

• Find All Possible Recipes from Given Supplies

Summary

• Find all the recipes that can be created with the given ingredients and supplies.

Approach

• Breadth-First Search (BFS) algorithm is used to traverse the graph of recipes and ingredients
• The algorithm starts by initializing a queue with all the recipes and a set of available supplies
• Then, it iteratively pops a recipe from the queue, checks if all its ingredients are available, and if so, adds it to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later.

Complexity

• O(N + M) where N is the number of recipes and M is the total number of ingredients

Explanation

• The algorithm uses a queue to keep track of the recipes to be processed and a set to keep track of the available supplies
• It iterates over the recipes and checks if all their ingredients are available
• If they are, it adds the recipe to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later
• This process continues until all recipes have been processed or the queue is empty.

Solution Code:

class Solution {
public:
    queue que;
    set supply;
    vector findAllRecipes(vector& recipes, vector>& ingredients, vector& supplies) {
        int N = recipes.size();
        
        for(int i = 0 ; i < N; i++){
            que.push(i);
        }
        for(int i = 0 ; i < supplies.size(); i++){
            supply.insert(supplies[i]);
        }
        vector ans;
        int cnt = 0;
        while(!que.empty() && cnt < N){
            int idx = que.front();
            que.pop();
            bool success = true;
            for(int i = 0; i < ingredients[idx].size(); i++){
                if(supply.find(ingredients[idx][i]) == supply.end()){
                    success = false;
                    break;
                }
            }
            if(success){
                supply.insert(recipes[idx]);
                ans.push_back(recipes[idx]);
                cnt = -1;
                N--;
            } else{
                que.push(idx);
            }
            cnt++;
        }
        return ans;
    }
};