경로 문제 | (38)

타잔 알고리즘 (Tarjan's Algorithm)

개념
타잔 알고리즘은 그래프에서 **강하게 연결된 컴포넌트(SCC, Strongly Connected Components)**를 찾는 알고리즘입니다.

• DFS 기반으로 동작하며, 각 노드의 발견 순서(low-link value)를 이용합니다.
• 방향 그래프에서 SCC를 탐색하는 데 유용합니다.

문제

1. Critical Connections in a Network (LeetCode 1192)
   설명: 네트워크에서 단일 연결을 끊으면 그래프가 분리되는 간선을 찾습니다.
   핵심 개념: Tarjan's Algorithm, DFS.
2. Strongly Connected Components (Custom Problem - 구현 필요)
   설명: 방향 그래프에서 모든 SCC를 탐지합니다.
   핵심 개념: Tarjan Algorithm, DFS.

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

개념
플로이드-워셜 알고리즘은 그래프에서 모든 쌍의 최단 경로를 계산하는 알고리즘입니다.

• 동적 프로그래밍을 사용하며, 가중치가 음수일 수도 있습니다(음수 사이클은 허용하지 않음).
• 인접 행렬 표현의 그래프에 적합합니다.

문제

1. All Pairs Shortest Path (Custom Problem - 구현 필요)
   설명: 방향 또는 무방향 그래프에서 모든 노드 쌍 간의 최단 경로를 계산합니다.
   핵심 개념: 플로이드-워셜 알고리즘.
2. Network Delay Time (LeetCode 743)
   설명: 네트워크에서 신호가 모든 노드에 도달하는 데 걸리는 시간을 계산합니다.
   핵심 개념: 그래프 탐색, 플로이드-워셜 가능.
3. City With the Smallest Number of Neighbors (LeetCode 1334)
   설명: 모든 도시에서 특정 거리 내에서 접근할 수 있는 도시의 수를 계산합니다.
   핵심 개념: 플로이드-워셜 또는 다익스트라.

Kosaraju Algorithm

개념
Kosaraju 알고리즘은 방향 그래프에서 SCC를 탐지하는 또 다른 알고리즘입니다.

• 두 번의 DFS를 수행합니다.
  1. 그래프의 역순(topological order)을 구함.
  2. 역 그래프(reverse graph)에서 SCC를 탐지.

문제

1. Find SCC in Directed Graph (Custom Problem - 구현 필요)
   설명: 방향 그래프의 모든 SCC를 탐지합니다.
   핵심 개념: Kosaraju Algorithm, DFS.
2. Connected Components in Graph (LeetCode 323)
   설명: 그래프의 연결 요소의 수를 계산합니다(방향성이 없는 그래프).
   핵심 개념: DFS, Union-Find (Kosaraju 알고리즘과 변형 가능).

다익스트라 알고리즘 (Dijkstra's Algorithm)

개념
다익스트라 알고리즘은 단일 시작점에서 모든 노드까지의 최단 경로를 찾습니다.

• BFS의 우선순위 큐(최소 힙) 버전입니다.
• 음수 가중치는 허용되지 않습니다.

문제

1. Network Delay Time (LeetCode 743)
   설명: 시작 노드에서 모든 노드에 신호가 도달하는 데 걸리는 시간을 계산합니다.
   핵심 개념: 다익스트라 알고리즘.
2. Cheapest Flights Within K Stops (LeetCode 787)
   설명: K번 이하의 스탑으로 목적지까지 가는 가장 저렴한 경로를 찾습니다.
   핵심 개념: 다익스트라 알고리즘.

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

개념
벨만-포드는 음수 가중치를 포함하는 그래프에서 단일 시작점에서 최단 경로를 찾습니다.

• 모든 간선을 반복적으로 업데이트합니다.
• 음수 사이클도 감지할 수 있습니다.

문제

1. Detect Negative Weight Cycle (Custom Problem - 구현 필요)
   설명: 그래프에 음수 가중치 사이클이 있는지 감지합니다.
   핵심 개념: 벨만-포드 알고리즘.
2. Find Minimum Cost Path (Custom Problem - 구현 필요)
   설명: 시작 노드에서 특정 노드까지의 최소 비용 경로를 찾습니다.
   핵심 개념: 벨만-포드 알고리즘.

위상정렬 (Topological Sorting)

개념
위상정렬은 **DAG(Directed Acyclic Graph)**에서 노드 순서를 구하는 방법입니다.

• 간선 방향에 따라 선행 조건이 만족되도록 순서를 정합니다.

문제

1. Course Schedule II (LeetCode 210)
   설명: 주어진 코스의 순서를 출력합니다.
   핵심 개념: 위상정렬, DFS, BFS.
2. Alien Dictionary (LeetCode 269 - Premium)
   설명: 외계어 사전의 단어 순서를 결정합니다.
   핵심 개념: 위상정렬, 그래프.
3. Parallel Courses (LeetCode 1136)
   설명: 모든 코스를 완료하는 데 필요한 최소 학기 수를 계산합니다.
   핵심 개념: 위상정렬, BFS.

 

싸이클이 없는 모든 경로를 출력

1. All Paths From Source to Target (LeetCode 797)
   설명: 방향 그래프에서 시작점부터 도착점까지의 모든 경로를 출력합니다.
   핵심 개념: DFS, 백트래킹.
2. Paths with Minimum Effort (LeetCode 1631)
   설명: 각 경로에서 최소 노력을 필요로 하는 모든 경로를 찾습니다.
   핵심 개념: BFS, 다익스트라.

싸이클이 없는 모든 경로 중 가장 짧은 경로를 찾는 문제

1. Cheapest Flights Within K Stops (LeetCode 787)
   설명: 주어진 그래프에서 K번 이내의 스탑으로 가장 저렴한 경로를 찾습니다.
   핵심 개념: 다익스트라, BFS.
2. Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368)
   설명: 격자에서 유효한 경로를 구성하는 데 필요한 최소 비용을 계산합니다.
   핵심 개념: BFS, 다익스트라.

싸이클이 없는 모든 경로 중 가장 긴 경로를 찾는 문제 (Brute-Force 방식, Backtracking)

1. Longest Path in a Directed Acyclic Graph (Custom Problem - 구현 필요)
   설명: DAG에서 모든 경로를 탐색하며 가장 긴 경로를 찾는 문제입니다.
   핵심 개념: DFS, 백트래킹.
   참고: 이 문제는 일반적인 LeetCode 문제로 제공되지 않지만, 그래프 탐색과 백트래킹을 연습할 수 있습니다.
2. Longest Increasing Path in a Matrix (LeetCode 329)
   설명: 2D 행렬에서 증가하는 경로 중 가장 긴 길이를 찾습니다.
   핵심 개념: DFS, 백트래킹, 메모이제이션.

방향이 있고 싸이클이 없는 그래프(DAG) + 위상정렬 사용하는 문제

1. Course Schedule II (LeetCode 210)
   설명: 주어진 코스의 순서를 출력합니다.
   핵심 개념: 위상정렬, BFS, DFS.
2. Minimum Height Trees (LeetCode 310)
   설명: 그래프에서 최소 높이를 가지는 루트 노드를 찾습니다.
   핵심 개념: 위상정렬, 그래프.
3. Parallel Courses (LeetCode 1136)
   설명: 모든 코스를 완료하는 데 필요한 최소 학기 수를 계산합니다.
   핵심 개념: 위상정렬, BFS.
4. Alien Dictionary (LeetCode 269 - Premium)
   설명: 외계어 사전의 순서를 결정합니다.
   핵심 개념: 위상정렬, 그래프.
5. Find Eventual Safe States (LeetCode 802)
   설명: 그래프에서 터미널 상태로 도달할 수 있는 모든 노드를 찾습니다.
   핵심 개념: 위상정렬, DFS.

추가 백트래킹 연습 문제

1. N-Queens (LeetCode 51)
   설명: N×N 체스판에서 N개의 퀸을 서로 공격하지 않도록 배치하는 모든 방법을 찾습니다.
   핵심 개념: 백트래킹.
2. Sudoku Solver (LeetCode 37)
   설명: 주어진 스도쿠 퍼즐을 해결합니다.
   핵심 개념: 백트래킹.
3. Word Search II (LeetCode 212)
   설명: 단어 목록에 있는 단어들을 격자에서 찾습니다.
   핵심 개념: 백트래킹, 트라이(Trie).
4. Generate Parentheses (LeetCode 22)
   설명: 균형 잡힌 괄호의 모든 조합을 생성합니다.
   핵심 개념: 백트래킹.
5. Combination Sum II (LeetCode 40)
   설명: 중복을 포함하지 않는 숫자의 조합으로 목표 합을 생성합니다.
   핵심 개념: 백트래킹.

추가 그래프 DFS/BFS 탐색 문제

1. Surrounded Regions (LeetCode 130)
   설명: 2D 격자에서 "O"를 "X"로 변환하며 경계 조건을 고려합니다.
   핵심 개념: DFS, BFS.
2. Pacific Atlantic Water Flow (LeetCode 417)
   설명: 물이 태평양과 대서양 모두로 흐를 수 있는 모든 격자를 찾습니다.
   핵심 개념: DFS, BFS.
3. Redundant Connection (LeetCode 684)
   설명: 그래프에서 사이클을 형성하는 간선을 찾습니다.
   핵심 개념: DFS, 유니온 파인드.
4. Clone Graph (LeetCode 133)
   설명: 그래프를 복제합니다.
   핵심 개념: DFS, BFS.
5. Network Delay Time (LeetCode 743)
   설명: 네트워크에서 모든 노드로 신호가 도달하는 데 걸리는 시간을 계산합니다.
   핵심 개념: 다익스트라, 그래프.

추가 위상정렬 기반 문제

1. Reconstruct Itinerary (LeetCode 332)
   설명: 항공권 리스트를 사용해 여행 일정을 재구성합니다.
   핵심 개념: 위상정렬, DFS.
2. Sequence Reconstruction (LeetCode 444 - Premium)
   설명: 여러 시퀀스가 주어질 때 고유한 원본 순서를 복원할 수 있는지 확인합니다.
   핵심 개념: 위상정렬, 그래프.
3. Longest Path in Directed Acyclic Graph (DAG) (Custom Problem - 구현 필요)
   설명: 방향성이 있고 싸이클이 없는 그래프에서 가장 긴 경로를 찾습니다.
   핵심 개념: DFS, DP.
4. Course Schedule III (LeetCode 630)
   설명: 제한 시간 내 최대 과목을 완료하는 방법을 찾습니다.
   핵심 개념: 위상정렬, 힙.

추가 심화 문제

1. Critical Connections in a Network (LeetCode 1192)
   설명: 네트워크에서 단일 연결을 끊으면 네트워크가 분리되는 간선을 찾습니다.
   핵심 개념: 그래프, 타잔 알고리즘.
2. Strongly Connected Components (Custom Problem - 구현 필요)
   설명: 방향 그래프에서 강하게 연결된 컴포넌트를 찾습니다.
   핵심 개념: Kosaraju 또는 Tarjan 알고리즘.