위상정렬 - Leetcode 문제(Medium 레벨)

1. BFS 큐 기반 위상 정렬 (Topological Sort using BFS - Kahn's Algorithm)

• Problem 1: Course Schedule III (LeetCode 630)
  • 설명: 주어진 수업들을 듣기 위한 최소 시간으로 완료할 수 있는 최대 수업 수를 구하는 문제입니다. BFS 기반의 위상 정렬을 사용하여 해결할 수 있습니다.
  • 핵심 개념: 위상 정렬, 큐, 진입 차수 (in-degree), 최적화
• Problem 2: Reconstruct Itinerary (LeetCode 332)
  • 설명: 공항 여행 계획을 재구성하는 문제입니다. 각 공항에서의 출발지와 도착지가 주어지며, 위상 정렬을 사용하여 경로를 찾습니다.
  • 핵심 개념: 그래프, 위상 정렬, 큐, 경로 탐색
• Problem 3: Task Scheduler II (LeetCode 621)
  • 설명: 주어진 작업들을 주어진 조건에서 완료하기 위한 최소 시간 내 작업 순서를 찾는 문제입니다. BFS로 큐를 사용하여 작업을 스케줄링합니다.
  • 핵심 개념: 큐, 위상 정렬, 진입 차수
• Problem 4: Minimum Height Trees (LeetCode 310)
  • 설명: 최소 높이를 가지는 트리의 루트를 찾는 문제입니다. 위상 정렬을 이용해 트리에서 가장 작은 높이를 가지는 루트를 찾습니다.
  • 핵심 개념: 위상 정렬, 트리, 큐
• Problem 5: Count of Smaller Numbers After Self (LeetCode 315)
  • 설명: 각 숫자 뒤에 있는 작은 숫자의 개수를 구하는 문제입니다. 트리 구조를 사용한 이진 검색 트리와 위상 정렬 개념을 활용하여 풀이할 수 있습니다.
  • 핵심 개념: 이진 검색 트리, 위상 정렬, 그래프

2. DFS 기반 위상 정렬

• Problem 1: Word Search II (LeetCode 212)
  • 설명: 주어진 단어 목록을 2D 보드에서 찾는 문제입니다. DFS로 그래프 탐색을 하면서 주어진 단어들을 찾을 수 있습니다.
  • 핵심 개념: DFS, 백트래킹, 그래프 탐색
• Problem 2: Redundant Connection II (LeetCode 685)
  • 설명: 주어진 그래프에서 싸이클을 찾고, 그 중에서 중복된 연결을 찾아내는 문제입니다. DFS를 사용해 그래프를 순회하면서 싸이클을 탐지합니다.
  • 핵심 개념: DFS, 싸이클 탐지, 그래프
• Problem 3: Course Schedule IV (LeetCode 365)
  • 설명: 수업들을 듣기 위한 선후 관계를 바탕으로 가능한 경로가 있는지 확인하는 문제입니다. DFS를 사용하여 위상 정렬을 구현하고 경로 존재 여부를 검사합니다.
  • 핵심 개념: 위상 정렬, DFS, 그래프 탐색
• Problem 4: Palindrome Partitioning II (LeetCode 132)
  • 설명: 주어진 문자열을 회문으로 분할하는 최소 분할 횟수를 구하는 문제입니다. DFS를 사용하여 회문 분할을 검사하고 최소 횟수를 찾습니다.
  • 핵심 개념: DFS, 백트래킹, 회문 검사
• Problem 5: Number of Islands (LeetCode 200)
  • 설명: 주어진 2D 맵에서 "섬"의 개수를 구하는 문제입니다. DFS를 사용하여 각 섬을 탐색합니다.
  • 핵심 개념: DFS, 그래프 탐색, 연결된 부분

3. BFS를 이용한 경로 찾기 (Path Finding with BFS)

• Problem 1: Word Ladder II (LeetCode 126)
  • 설명: 주어진 단어들을 이용해 최소 횟수로 변환할 수 있는 경로를 모두 구하는 문제입니다. BFS로 최단 경로를 구합니다.
  • 핵심 개념: BFS, 최단 경로, 그래프 탐색
• Problem 2: Shortest Path in a Grid with Obstacles Elimination (LeetCode 1293)
  • 설명: 장애물을 제거하면서 주어진 그리드에서 최단 경로를 구하는 문제입니다. BFS를 사용해 장애물 제거 횟수를 고려하며 경로를 찾습니다.
  • 핵심 개념: BFS, 최단 경로, 2D 그리드
• Problem 3: Open the Lock (LeetCode 752)
  • 설명: 자물쇠를 열기 위한 최소 횟수를 구하는 문제입니다. BFS를 사용하여 자물쇠 상태를 탐색하고 최단 경로를 구합니다.
  • 핵심 개념: BFS, 상태 탐색, 그래프 탐색
• Problem 4: Minimum Moves to Reach Target with Rotations (LeetCode 1289)
  • 설명: 회전 가능한 배열에서 목표 지점까지 최소 이동 횟수를 구하는 문제입니다. BFS를 사용하여 회전 상태를 탐색합니다.
  • 핵심 개념: BFS, 상태 탐색, 최단 경로
• Problem 5: Escape the Ghosts (LeetCode 789)
  • 설명: 주어진 유령들로부터 탈출하는 문제입니다. BFS를 사용하여 유령들과의 거리를 계산하고 탈출 가능한지 확인합니다.
  • 핵심 개념: BFS, 최단 경로, 상태 탐색

4. 심벌 그래프 (Symbol Graph)

• Problem 1: Evaluate Division (LeetCode 399)
  • 설명: 수학 식을 계산하는 문제입니다. 그래프 탐색을 통해 각 변수들 간의 관계를 찾고 DFS나 BFS로 값을 계산합니다.
  • 핵심 개념: 그래프 탐색, DFS/BFS, 심벌 그래프
• Problem 2: Social Network (LeetCode 731)
  • 설명: 주어진 소셜 네트워크에서 친구 관계를 찾고, 관계의 길이를 구하는 문제입니다. 그래프 탐색을 통해 친구 관계를 탐색합니다.
  • 핵심 개념: 그래프, BFS/DFS, 연결된 컴포넌트
• Problem 3: Detect Capital (LeetCode 520)
  • 설명: 주어진 단어에서 대소문자 규칙을 만족하는지 확인하는 문제입니다. 이 문제는 그래프 이론을 통해 심벌 규칙을 확인할 수 있습니다.
  • 핵심 개념: 그래프, 규칙 검사, 대소문자 처리
• Problem 4: Smallest String with Swaps (LeetCode 1202)
  • 설명: 주어진 문자들에 대해 가능한 스왑으로 사전 순서 가장 작은 문자열을 만드는 문제입니다. 그래프 탐색을 통해 가능한 스왑을 찾습니다.
  • 핵심 개념: 그래프, 연결된 컴포넌트, 스왑
• Problem 5: Number of Connected Components in an Undirected Graph (LeetCode 323)
  • 설명: 주어진 무방향 그래프에서 연결된 컴포넌트의 수를 구하는 문제입니다. DFS나 BFS를 사용하여 그래프의 연결성을 탐색합니다.
  • 핵심 개념: DFS/BFS, 그래프 탐색, 연결된 컴포넌트

5. 위상 정렬로 싸이클 찾기 (Cycle Detection using Topological Sort)

• Problem 1: Graph Valid Tree (LeetCode 261)
  • 설명: 주어진 그래프가 유효한 트리인지 확인하는 문제입니다. 위상 정렬을 통해 그래프에서 싸이클을 찾고 트리 여부를 판별합니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 그래프
• Problem 2: Course Schedule IV (LeetCode 365)
  • 설명: 주어진 수업들 간의 선후 관계를 만족하는지 확인하는 문제로, 위상 정렬을 사용하여 싸이클 탐지를 진행할 수 있습니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 그래프
• Problem 3: Accounts Merge (LeetCode 721)
  • 설명: 여러 계정들이 주어졌을 때 중복된 계정을 합치는 문제입니다. 그래프를 사용하여 사람들의 관계를 파악하고, 이를 통해 계정들을 합칩니다.
  • 핵심 개념: 그래프, 연결된 컴포넌트, 싸이클 탐지
• Problem 4: Topological Sort (LeetCode 444)
  • 설명: 주어진 그래프의 위상 정렬을 수행하는 문제입니다. 싸이클이 없는지 확인하고, 가능하다면 위상 정렬을 반환합니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 진입 차수
• Problem 5: Tasks Scheduler (LeetCode 621)
  • 설명: 주어진 작업들을 스케줄링하는 문제로, 위상 정렬을 사용하여 작업 순서를 결정하고, 싸이클 탐지를 수행합니다.
  • 핵심 개념: 위상 정렬, 큐, 싸이클 탐지