주어진 보급품에서 가능한 모든 레시피 찾기

n개의 다양한 요리법에 대한 정보가 있습니다. 문자열 배열recipes과 2D 문자열 배열ingredients이 제공됩니다. ith 레시피의 이름은 recipes[i] 이며, ingredients[i] 에서 필요한 모든 재료가 있으면 만들 수 있습니다. 레시피의 재료는 다른 레시피에서 생성해야 할 수 있습니다. 즉, ingredients[i]에는 recipes에 있는 문자열이 포함될 수 있습니다.

또한 초기에 가지고 있는 모든 재료를 포함하는 문자열 배열supplies이 제공되며 모든 재료를 무한정 공급할 수 있습니다.

생성할 수 있는 모든 레시피 목록을 반환합니다. 어떤 순서로든 답변을 반환할 수 있습니다.

두 레시피는 재료에 서로를 포함할 수 있습니다.

예 1:

입력: recipes = ["빵"], 재료 = [["효모","밀가루"]], 공급 = ["효모","밀가루","옥수수"]
출력: ["빵"]
설명:
"이스트"와 "밀가루"라는 재료가 있기 때문에 "빵"을 만들 수 있습니다.

예 2:

입력: recipes = ["빵","샌드위치"], 재료 = [["효모","밀가루"],["빵","고기"]], 공급 = ["효모","밀가루","고기"]
출력: ["빵","샌드위치"]
설명:
"이스트"와 "밀가루"라는 재료가 있기 때문에 "빵"을 만들 수 있습니다.
재료 "고기"가 있고 재료 "빵"을 만들 수 있으므로 "샌드위치"를 만들 수 있습니다.

예 3:

입력: recipes = ["빵","샌드위치","버거"], 재료 = [["효모","밀가루"],["빵","고기"],["샌드위치","고기", "빵"]], 용품 = ["효모","밀가루","고기"]
출력: ["빵","샌드위치","버거"]
설명:
"이스트"와 "밀가루"라는 재료가 있기 때문에 "빵"을 만들 수 있습니다.
재료 "고기"가 있고 재료 "빵"을 만들 수 있으므로 "샌드위치"를 만들 수 있습니다.
"고기"라는 재료가 있고 "빵"과 "샌드위치"라는 재료가 있으므로 "버거"를 만들 수 있습니다.

제약:

n == recipes.length == ingredients.length

1 <= n <= 100

1 <= ingredients[i].length, supplies.length <= 100

1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10

recipes[i], ingredients[i][j] 및 supplies[k]는 영문 소문자로만 구성됩니다.

결합된 recipes 및 supplies의 모든 값은 고유합니다.

각각ingredients[i]에 중복 값이 ​​없습니다.

해결책:

class Solution:
    def topologicalSort(self, graph, node, visited, stack, pos):
        visited.add(node)
        for n in graph.get(node, []):
            if n not in visited:
                self.topologicalSort(graph, n, visited, stack, pos)
        if node in pos:
            stack.append(pos[node])

    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        graph = {}
        supplies = set(supplies)
        n = len(recipes)
        for i in range(n):
            for item in ingredients[i]:
                graph[item] = graph.get(item, []) + [recipes[i]]
        pos = {}
        for i, item in enumerate(recipes):
            pos[item] = i
        stack = []
        visited = set()
        for node in graph:
            if node not in visited:
                self.topologicalSort(graph, node, visited, stack, pos)
        for i in stack[::-1]:
            valid = True
            for item in ingredients[i]:
                if item not in supplies:
                    valid = False
                    break
            if valid:
                supplies.add(recipes[i])
            else:
                recipes[i] = False
        return [r for r in recipes if r]