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

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

• Problem 1: Course Schedule (LeetCode 207)
  • 설명: 수업들 간의 선후 관계를 바탕으로 모든 수업을 듣기 위한 가능한 순서를 찾는 문제입니다. 위상 정렬을 사용하여 해결할 수 있습니다.
  • 핵심 개념: 큐, 진입 차수 (in-degree), 위상 정렬
• Problem 2: Course Schedule II (LeetCode 210)
  • 설명: Course Schedule 문제와 비슷하지만, 가능한 수업 순서를 반환하는 문제입니다. BFS를 사용하여 위상 정렬을 수행하여 순서를 구합니다.
  • 핵심 개념: 큐, 진입 차수, 위상 정렬, 수업 순서
• Problem 3: Alien Dictionary (LeetCode 269)
  • 설명: 외계어 사전의 알파벳 순서를 결정하는 문제입니다. 위상 정렬을 사용하여 문자 간의 관계를 정의하고 사전 순서를 구합니다.
  • 핵심 개념: 그래프, 위상 정렬, 큐
• Problem 4: Eventual Safe States (LeetCode 802)
  • 설명: 그래프에서 안전한 상태를 찾는 문제로, 위상 정렬을 통해 싸이클을 확인하고 안전한 상태를 찾을 수 있습니다.
  • 핵심 개념: 큐, 진입 차수, 위상 정렬
• Problem 5: Tasks Scheduler (LeetCode 621)
  • 설명: 주어진 작업들을 최소한의 시간 내에 완료하는 문제로, 위상 정렬을 활용하여 순서를 계산할 수 있습니다.
  • 핵심 개념: 큐, 위상 정렬, 진입 차수

2. DFS 기반 위상 정렬

• Problem 1: Find Eventual Safe States (LeetCode 802)
  • 설명: 안전한 상태를 찾는 문제로, DFS를 통해 위상 정렬을 사용하여 안전 여부를 판단합니다.
  • 핵심 개념: DFS, 위상 정렬, 싸이클 탐지
• Problem 2: Sequence Reconstruction (LeetCode 444)
  • 설명: 주어진 순서들로부터 유일한 수열을 복원할 수 있는지 확인하는 문제입니다. DFS 기반 위상 정렬을 사용하여 유일성을 판단합니다.
  • 핵심 개념: DFS, 위상 정렬, 유일성 검사
• Problem 3: Graph Valid Tree (LeetCode 261)
  • 설명: 주어진 그래프가 트리인지 아닌지 판별하는 문제입니다. DFS를 사용하여 트리의 유효성을 검사할 수 있습니다.
  • 핵심 개념: DFS, 연결성, 그래프 탐색
• Problem 4: Number of Connected Components in an Undirected Graph (LeetCode 323)
  • 설명: 주어진 무방향 그래프에서 연결된 컴포넌트의 개수를 구하는 문제입니다. DFS를 사용하여 연결된 부분을 탐색합니다.
  • 핵심 개념: DFS, 연결된 컴포넌트, 그래프 탐색
• Problem 5: Clone Graph (LeetCode 133)
  • 설명: 그래프의 복사본을 만드는 문제로, DFS를 사용하여 원본 그래프를 깊이 우선으로 탐색하여 새로운 그래프를 만듭니다.
  • 핵심 개념: DFS, 그래프 탐색, 클론

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

• Problem 1: Word Ladder (LeetCode 127)
  • 설명: 주어진 단어들로 단어 사다리를 구성하는 문제입니다. BFS를 사용하여 단어 간 최소 변환 횟수를 구합니다.
  • 핵심 개념: BFS, 최단 경로, 그래프 탐색
• Problem 2: Shortest Path in Binary Matrix (LeetCode 1091)
  • 설명: 0과 1로 이루어진 이진 행렬에서 시작점에서 끝점으로의 최단 경로를 구하는 문제입니다.
  • 핵심 개념: BFS, 최단 경로, 2D 그래프
• Problem 3: Open the Lock (LeetCode 752)
  • 설명: 자물쇠를 여는 문제로, BFS를 사용하여 가장 빠른 방법을 구합니다.
  • 핵심 개념: BFS, 최단 경로, 상태 공간 탐색
• Problem 4: Binary Tree Level Order Traversal (LeetCode 102)
  • 설명: 이진 트리에서 각 레벨을 순서대로 출력하는 문제입니다. BFS를 사용하여 트리를 레벨별로 탐색합니다.
  • 핵심 개념: BFS, 트리 탐색, 레벨 순서
• Problem 5: Snake and Ladder (LeetCode 849)
  • 설명: 주어진 보드에서 시작점에서 끝점까지 가는 최소 이동 횟수를 구하는 문제입니다. BFS를 사용하여 경로를 탐색합니다.
  • 핵심 개념: BFS, 최단 경로, 상태 탐색

4. 심벌 그래프 (Symbol Graph)

• Problem 1: Evaluate Division (LeetCode 399)
  • 설명: 주어진 식을 계산하는 문제로, 그래프를 통해 각 변수 간의 관계를 나타내고 DFS/BFS를 통해 값을 계산합니다.
  • 핵심 개념: 그래프, DFS, BFS, 심벌 그래프
• Problem 2: Graph Valid Tree (LeetCode 261)
  • 설명: 주어진 그래프가 트리인지 확인하는 문제입니다. 그래프가 트리인지 확인하는 데 DFS 또는 BFS로 연결성을 탐색할 수 있습니다.
  • 핵심 개념: 그래프 탐색, 트리, 연결성 검사
• Problem 3: Number of Connected Components in an Undirected Graph (LeetCode 323)
  • 설명: 무방향 그래프에서 연결된 컴포넌트의 개수를 구하는 문제입니다. DFS나 BFS로 그래프를 탐색하여 연결된 부분을 셀 수 있습니다.
  • 핵심 개념: 그래프 탐색, 연결된 컴포넌트, BFS/DFS
• Problem 4: Clone Graph (LeetCode 133)
  • 설명: 그래프를 복제하는 문제로, DFS나 BFS를 이용하여 원본 그래프의 각 노드를 복제하고 복사본을 만들어냅니다.
  • 핵심 개념: 그래프 탐색, BFS/DFS, 복제
• Problem 5: Friend Circles (LeetCode 547)
  • 설명: 학생들이 서로 친구인 관계를 나타내는 2D 배열을 기반으로 친구 그룹을 찾는 문제입니다. 그래프 탐색을 통해 친구 그룹을 구할 수 있습니다.
  • 핵심 개념: 그래프, DFS/BFS, 연결된 컴포넌트

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

• Problem 1: Course Schedule (LeetCode 207)
  • 설명: 주어진 수업들 간의 선후 관계를 바탕으로 모든 수업을 듣기 위한 가능한 순서를 찾는 문제입니다. 위상 정렬을 통해 싸이클이 있는지 확인할 수 있습니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 진입 차수 (in-degree)
• Problem 2: Course Schedule II (LeetCode 210)
  • 설명: Course Schedule 문제와 비슷하지만, 이 문제에서는 가능한 수업 순서를 반환해야 합니다. 위상 정렬을 수행하여 싸이클을 찾을 수 있습니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 진입 차수
• Problem 3: Alien Dictionary (LeetCode 269)
  • 설명: 외계어 사전에서 알파벳 순서를 찾는 문제입니다. 위상 정렬을 사용하여 문자 간의 관계를 정의하고, 그 과정에서 싸이클이 존재하는지 확인합니다.
  • 핵심 개념: 위상 정렬, 그래프 탐색, 싸이클 탐지
• Problem 4: Find Eventual Safe States (LeetCode 802)
  • 설명: 그래프에서 안전한 상태를 찾는 문제로, 위상 정렬을 통해 싸이클을 확인하고 안전한 상태를 찾을 수 있습니다.
  • 핵심 개념: 위상 정렬, 싸이클 탐지, 안전 상태, 그래프
• Problem 5: Redundant Connection (LeetCode 684)
  • 설명: 주어진 그래프에서 중복된 연결을 찾아내는 문제입니다. 싸이클을 찾는 방식으로 해결할 수 있으며, 이 문제에서 싸이클이 발생하는 연결을 식별해야 합니다.
  • 핵심 개념: 싸이클 탐지, 그래프 탐색, 연결성