---

0. 문제

당신은 서로 다른 n개의 요리 레시피에 대한 정보를 가지고 있다.

문자열 배열 recipes와 2차원 문자열 배열 ingredients가 주어진다. i번째 레시피는 recipes[i]라는 이름을 가지며, 이 레시피를 만들기 위해 필요한 재료는 ingredients[i]에 명시되어 있다. 하나의 레시피는 다른 레시피의 재료가 될 수도 있다. 즉, ingredients[i]에는 recipes에 있는 문자열이 포함될 수 있다.

또한, 문자열 배열 supplies가 주어지며 이는 처음부터 가지고 있는 재료들을 나타낸다. 이 재료들은 무한히 사용할 수 있다.

목표: 만들 수 있는 모든 레시피의 리스트를 반환하라.
결과의 순서는 자유롭다.

참고: 두 개의 레시피가 서로의 재료로 포함될 수도 있다.

예제 1.

• 입력:
  recipes = ["bread"]
  ingredients = [["yeast","flour"]]
  supplies = ["yeast","flour","corn"]

• 출력:
  ["bread"]

• 설명:

  "yeast"와 "flour"가 모두 있으므로 "bread"를 만들 수 있다.

예제 2.

• 입력:
  recipes = ["bread","sandwich"]
  ingredients = [["yeast","flour"],["bread","meat"]]
  supplies = ["yeast","flour","meat"]

• 출력:
  ["bread","sandwich"]

• 설명:

  "bread"는 "yeast"와 "flour"로 만들 수 있고, "sandwich"는 "meat"와 이미 만들 수 있는 "bread"로 만들 수 있다.

예제 3.

• 입력:
  recipes = ["bread","sandwich","burger"]
  ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]]
  supplies = ["yeast","flour","meat"]

• 출력:
  ["bread","sandwich","burger"]

• 설명:

  "bread"는 바로 만들 수 있음
  "sandwich"는 "bread"와 "meat"로 만들 수 있음
  "burger"는 "sandwich", "bread", "meat"로 만들 수 있음

제한사항

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]에는 중복된 값이 없음

---

1. 개념

1.1 BFS (Breadth-First Search, 너비 우선 탐색)

✅ 개념 정의

BFS는 그래프 또는 트리에서 가까운 노드부터 탐색하는 알고리즘.
시작 정점에서부터 거리가 가까운 노드를 먼저 방문하고, 점점 멀리 있는 노드로 확장해 나간다.

• 큐(Queue) 자료구조를 사용
• 최단 거리 탐색에 적합 (예: 미로 문제)

🎯 핵심 특징

항목	내용
탐색 순서	가까운 노드 → 먼 노드
자료구조 사용	큐(Queue)
대표적 사용 사례	최단 거리 탐색, 경로 찾기, 레벨 탐색
시간 복잡도	O(V + E) (V: 정점, E: 간선)

🔧 알고리즘 원리

1. 시작 정점을 큐에 넣고 방문 처리
2. 큐에서 노드를 하나 꺼냄
3. 꺼낸 노드와 연결된 모든 이웃 노드에 대해:
   - 방문하지 않았다면 큐에 삽입하고 방문 처리
4. 큐가 빌 때까지 반복

🧠 예시

입력 그래프

A - B
|   |
C - D

탐색 순서 (시작: A)

1. 큐: [A]
2. 방문: A → 큐에 B, C 추가 → [B, C]
3. 방문: B → 큐에 D 추가 → [C, D]
4. 방문: C → 이미 방문한 노드 생략 → [D]
5. 방문: D → 끝

최종 방문 순서: A → B → C → D

🔍 BFS vs DFS 비교

항목	BFS	DFS
방식	큐 사용	스택 or 재귀 사용
순서	가까운 노드 먼저	깊은 노드 먼저
용도	최단 거리	경로/백트래킹 문제
구현	반복문(큐)	재귀 or 스택

---

1.2 Topological Sort (위상 정렬)

✅ 개념 정의

위상 정렬이란, 방향 그래프(Directed Graph)에서 선행 관계(Dependency)를 만족하도록 정점들을 순서대로 나열하는 정렬 방식.

• 예: "A 작업 → B 작업"이라면, B보다 A를 먼저 나와야 함.
• DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서만 가능함

⚠️ 전제 조건

• 그래프는 방향 그래프여야 함
• 사이클이 없어야 함 (A → B → C → A 같은 순환 X)

🔧 알고리즘 원리

진입 차수(in-degree)를 기준으로 정렬 순서를 결정함.

1. 진입 차수 개념

   • 어떤 정점에 화살표로 들어오는 간선의 개수
   • 진입 차수가 0인 정점 → 선행 조건이 없는 작업 → 가장 먼저 수행 가능

2. 기본 알고리즘 (Kahn’s Algorithm)

1. 각 노드의 진입 차수(in-degree)를 계산
2. 진입 차수가 0인 노드를 큐에 삽입
3. 큐에서 노드를 꺼내어 결과에 추가
   - 해당 노드와 연결된 간선 제거
   - 연결된 노드들의 진입 차수를 1씩 감소
   - 진입 차수가 0이 된 노드를 다시 큐에 삽입
4. 큐가 빌 때까지 반복

🧠 예시

A → C
B → C
C → D

진입 차수: A(0), B(0), C(2), D(1)

순서:

1. A, B 진입차수 0 → 큐에 삽입
2. A 제거 → C 진입차수 1
3. B 제거 → C 진입차수 0 → C 삽입
4. C 제거 → D 진입차수 0 → D 삽입
5. 최종 결과: A, B, C, D (혹은 B, A, C, D 등 가능)

---

2. 풀이

2.1 BFS

$O(n*m + s)$

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        // supplies의 모든 항목 available HashSet에 저장.
        Set<String> available = new HashSet<>();
        for (String supply: supplies)
            available.add(supply);

        // recipes의 인덱스를 recipeQueue에 모두 저장.
        Queue<Integer> recipeQueue = new LinkedList<>();
        for (int i = 0; i < recipes.length; i++)
            recipeQueue.add(i);

        List<String> createdRecipes = new ArrayList<>();
        int lastSize = -1;

        // 새로운 재료를 찾았다면 recipeQueue에 있는 recipe 재검토 필요.
        while (available.size() > lastSize) {
            lastSize = available.size();
            int queueSize = recipeQueue.size();

            // 각 recipe가 현재 available에 있는 재료로 만들어 질 수 있는지 확인.
            while (queueSize > 0) {
                queueSize--;
                int recipeIndex = recipeQueue.poll();
                boolean canCreate = true;

                // 현재 recipe에서 필요한 재료들이 available에 있는지 확인.
                for (String ingredient: ingredients.get(recipeIndex)) {
                    // 재료가 현재 available에 없다면 canCreate false, break
                    if (!available.contains(ingredient)) {
                        canCreate = false;
                        break;
                    }
                }

                // 만들 수 없는 recipe는 다시 recipeQueue 최후방으로
                // ... 나중에 새로운 재료가 추가되면 가능해질지도 모르니까!
                if (!canCreate)
                    recipeQueue.add(recipeIndex);
                // 만들 수 있는 recipe는 createdRecipe에 추가 + 새로운 재료로서 available에 추가
                else {
                    available.add(recipes[recipeIndex]);
                    createdRecipes.add(recipes[recipeIndex]);
                }
            }
        }
        return createdRecipes;
    }
}

---

2.2 Topological Sort

$O(n + m + s)$

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        // ingredient로 사용 가능한 supply 집합
        Set<String> availableSupply = new HashSet<>();
        for (String supply: supplies)
            availableSupply.add(supply);

        // recipe의 이름과 인덱스를 맵핑
        Map<String, Integer> recipeToIndex = new HashMap<>();
        for (int i = 0; i < recipes.length; i++)
            recipeToIndex.put(recipes[i], i);

        // reciee의 이름과 recipe의 재료를 맵핑
        Map<String, List<String>> dependencyGraph = new HashMap<>();

        // 각 recipe 별로 supply에서 제공하지 않는 ingredient 개수
        int[] inDegree = new int[recipes.length];

        // dependency graph 만들기
        for (int i = 0; i < recipes.length; i++) {
            // 각 recipe가 요구하는 재료를 확인
            for (String ingredient: ingredients.get(i)) {
                // supply에서 제공하지 않는 재료는 dependencyGraph와 inDegree에 추가
                if (!availableSupply.contains(ingredient)) {
                    // ingredient를 재료로 하는 repice List 생성 및 추가
                    dependencyGraph.putIfAbsent(ingredient, new ArrayList<String>());
                    dependencyGraph.get(ingredient).add(recipes[i]);
                    // 해당 recipe에 대응되는 index의 차수 1 증가
                    inDegree[i]++;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // inDegree가 0인, supply만으로 만들 수 있는 recipe를 queue에 추가.
        for (int i = 0; i < recipes.length; i++)
            if (inDegree[i] == 0)
                queue.add(i);

        List<String> createdRecipes = new ArrayList<>();
        // 위상 정렬
        while (!queue.isEmpty()) {
            // 현재 만들 수 있는 recipe 하나 꺼내기
            int recipeIndex = queue.poll();
            String recipe = recipes[recipeIndex];
            createdRecipes.add(recipe);

            // 현재 선택한 recipe를 재료로 하는 다른 recipe가 없는 경우
            if (!dependencyGraph.containsKey(recipe))
                continue;

            // 현재 선택한 recipe를 재료로 하는 다른 recipe가 있는 경우
            for (String depedentRecipe: dependencyGraph.get(recipe)) {
                // 현재 recipe가 재료인 recipe들의 차수 하나씩 감소 시키고,
                // 만약 차수가 0이 되는 recipe가 있다면 queue에 넣기.
                if (--inDegree[recipeToIndex.get(depedentRecipe)] == 0)
                    queue.add(recipeToIndex.get(depedentRecipe));
            }
        }
        return createdRecipes;
    }
}