트리+그래프+DP 심화 (릿코드12문제)

트리나 그래프에서 DP를 적용하는 문제들은 주로 다음과 같은 특징을 가지고 있습니다:

---

트리 + DP 문제의 특징

1. 최적 하위 구조 (Optimal Substructure):
   • 각 노드에서의 최적 값(예: 최대 합, 최대 경로 길이 등)은 자식 노드들의 결과를 바탕으로 계산됩니다.
   • 예: Binary Tree Maximum Path Sum (LeetCode 124).
2. DFS 기반 구현:
   • 트리의 구조를 탐색하며 하위 문제를 해결합니다.
   • DFS(깊이 우선 탐색)로 트리를 순회하며 값을 업데이트합니다.
   • 예: 트리의 독립 집합 (Largest Independent Set).
3. 메모이제이션을 통한 중복 계산 방지:
   • 각 노드에서 계산한 값을 저장해 동일한 계산을 반복하지 않도록 합니다.
   • 예: Diameter of Binary Tree (LeetCode 543).

---

그래프 + DP 문제의 특징

1. 다양한 최단 경로 알고리즘과 결합:
   • 그래프의 특정 경로(최단 경로, 최대 경로 등)를 구하는 문제에서 DP를 활용합니다.
   • 예: Floyd-Warshall (BOJ 11404).
2. DAG(방향성 비순환 그래프)와의 결합:
   • 방향성 비순환 그래프(DAG)는 위상 정렬을 통해 각 노드의 상태를 계산할 수 있습니다.
   • 예: Longest Path in a DAG.
3. 상태 전이 다이어그램:
   • 각 노드의 상태를 DP 배열로 저장하고, 상태 전이 규칙을 정의해 다음 상태를 계산합니다.
   • 예: Word Ladder II (LeetCode 126).
4. 재귀 + 메모이제이션 또는 반복문 활용:
   • 그래프 탐색과 DP를 결합하여 최적 경로를 구합니다.
   • 예: Network Delay Time (LeetCode 743).

---

구체적인 결합 예

트리 + DP:

• Binary Tree Maximum Path Sum (LeetCode 124):
  트리에서 특정 경로의 최대 합을 찾는 문제로, 각 노드에서 DP를 통해 경로 값을 누적하여 계산합니다.

그래프 + DP:

• Floyd-Warshall (BOJ 11404):
  모든 쌍의 최단 경로를 DP 배열에 저장하고, 반복적으로 갱신하는 방식으로 해결합니다.

---

1. 트리 기반 문제 (Tree Problems)

1.1. 트리에서 최대 독립 집합 (Largest Independent Set)

• Problem 1: Binary Tree Maximum Path Sum (LeetCode 124)
  설명: 이진 트리에서 최대 경로 합을 계산합니다.
  핵심 개념: 트리 탐색, DP.
  LeetCode 124
• Problem 2: 트리의 독립 집합 (BOJ 관련 문제)
  설명: 트리에서 서로 연결되지 않은 노드들의 최대 독립 집합 크기를 계산합니다.
  핵심 개념: 트리 탐색, DP.

1.2. 트리에서의 최소 경로 합

• Problem 3: Path Sum (LeetCode 112)
  설명: 루트에서 리프 노드로의 경로 중 합이 주어진 값과 같은 경로가 있는지 확인합니다.
  핵심 개념: 트리 탐색, 재귀.
  LeetCode 112
• Problem 4: Maximum Depth of Binary Tree (LeetCode 104)
  설명: 이진 트리의 최대 깊이를 계산합니다.
  핵심 개념: 트리 탐색, 재귀.
  LeetCode 104
• Problem 5: Diameter of Binary Tree (LeetCode 543)
  설명: 이진 트리에서 가장 긴 경로(지름)를 찾습니다.
  핵심 개념: 트리 탐색, DP.
  LeetCode 543

---

2. 그래프 기반 문제 (Graph Problems)

2.1. 최단 경로 문제

• Problem 6: Network Delay Time (LeetCode 743)
  설명: 네트워크에서 신호가 모든 노드에 도달하는 데 걸리는 최소 시간을 계산합니다.
  핵심 개념: 다익스트라 알고리즘, 그래프 탐색, DP.
  LeetCode 743
• Problem 7: Minimum Cost to Reach Destination in Time (LeetCode 1928)
  설명: 시간 제한 내에서 목적지에 도달하는 최소 비용을 계산합니다.
  핵심 개념: 그래프 탐색, DP.
  LeetCode 1928
• Problem 8: Floyd-Warshall All-Pairs Shortest Path (BOJ 11404)
  설명: 모든 쌍의 최단 경로를 계산합니다.
  핵심 개념: 플로이드-워셜 알고리즘, DP.
  BOJ 11404

---

2.2. 그래프 경로 문제

• Problem 9: Unique Paths III (LeetCode 980)
  설명: 격자에서 시작점과 끝점을 포함하는 모든 고유 경로의 수를 계산합니다.
  핵심 개념: 그래프 탐색, 백트래킹, DP.
  LeetCode 980
• Problem 10: Word Ladder II (LeetCode 126)
  설명: 시작 단어에서 목표 단어로 변환하기 위한 가장 짧은 경로를 계산합니다.
  핵심 개념: 그래프 탐색, BFS, DP.
  LeetCode 126

---

2.3. 최장 경로 문제

• Problem 11: Longest Path in a DAG (BOJ 관련 문제)
  설명: 방향성 비순환 그래프(DAG)에서 가장 긴 경로의 길이를 찾습니다.
  핵심 개념: 그래프 탐색, DP.
• Problem 12: Word Ladder (LeetCode 127)
  설명: 시작 단어에서 목표 단어로 변환하기 위한 최소 단계를 계산합니다.
  핵심 개념: BFS, 그래프 탐색.
  LeetCode 127

---

2.4. 기타 그래프 문제

• Problem 13: Detect Cycle in a Directed Graph (BOJ 2667)
  설명: 방향성 그래프에서 사이클이 존재하는지 확인합니다.
  핵심 개념: DFS, 위상 정렬.
  BOJ 2667
• Problem 14: Critical Connections in a Network (LeetCode 1192)
  설명: 그래프에서 단절선을 찾아냅니다.
  핵심 개념: 그래프 탐색, 타잔 알고리즘.
  LeetCode 1192

---

3. 혼합 트리와 그래프 문제

• Problem 15: Tree Diameter (LeetCode 543)
  설명: 트리의 지름(가장 긴 경로의 길이)을 계산합니다.
  핵심 개념: DFS, 트리 탐색.
  LeetCode 543
• Problem 16: Binary Tree Longest Consecutive Sequence (LeetCode 298)
  설명: 이진 트리에서 가장 긴 연속 증가 경로를 찾습니다.
  핵심 개념: DFS, 재귀.
  LeetCode 298