경로문제 || (25)

모든 정점을 방문하고 시작점으로 다시 돌아오는 모든 경로를 찾는 문제

1. All Paths From Source to Target (LeetCode 797)
   설명: 방향 그래프에서 시작점부터 끝점까지 모든 가능한 경로를 찾습니다.
   핵심 개념: DFS, 백트래킹.
2. Find All Possible Paths (Custom Problem - 구현 필요)
   설명: 모든 정점을 방문하는 모든 경로를 출력합니다.
   핵심 개념: DFS, 백트래킹.
3. Word Search (LeetCode 79)
   설명: 2D 그리드에서 주어진 단어를 찾는 경로를 출력합니다.
   핵심 개념: DFS, 백트래킹.

 

모든 정점을 방문하고 시작점으로 다시 돌아오는 모든 경로를 찾아서 모든 경로의 가중치 합을 구하는 문제

1. Cheapest Flights Within K Stops (LeetCode 787)
   설명: 주어진 그래프에서 특정 경로를 이동하며 최소 비용을 계산합니다.
   핵심 개념: BFS, 다익스트라.
2. Network Delay Time (LeetCode 743)
   설명: 시작점에서 다른 모든 노드로의 경로와 시간을 계산합니다.
   핵심 개념: 다익스트라, BFS.
3. Path With Maximum Probability (LeetCode 1514)
   설명: 주어진 그래프에서 경로 가중치가 확률로 주어질 때, 최대 확률 경로를 찾습니다.
   핵심 개념: 다익스트라, BFS.

 

모든 정점을 방문하고 시작점으로 다시 돌아오는 경로 중에서 가중치의 합이 가장 적은 경로를 찾아내는 문제

1. Traveling Salesman Problem (TSP) (Custom Problem - 구현 필요)
   설명: 모든 정점을 방문하는 최소 비용 경로를 찾습니다.
   핵심 개념: DP, 비트마스크.
2. Minimum Cost to Make at Least One Valid Path in a Grid (LeetCode 1368)
   설명: 주어진 그리드에서 최소 비용으로 유효한 경로를 찾습니다.
   핵심 개념: 다익스트라, BFS.
3. Shortest Path Visiting All Nodes (LeetCode 847)
   설명: 모든 노드를 한 번씩 방문하는 가장 짧은 경로의 길이를 찾습니다.
   핵심 개념: BFS, 비트마스크 DP.
4. Minimum Cost to Connect All Points (LeetCode 1584)
   설명: 모든 점을 연결하는 최소 비용을 계산합니다.
   핵심 개념: 최소 스패닝 트리, 프림 또는 크루스칼 알고리즘.

 

여행하는 외판원 문제

1. Shortest Path Visiting All Nodes (LeetCode 847)
   설명: 모든 노드를 방문하고 최소 거리를 계산합니다.
   핵심 개념: BFS, DP.
2. Minimum Cost to Connect All Points (LeetCode 1584)
   설명: 모든 점을 연결하는 최소 비용을 계산합니다.
   핵심 개념: 최소 스패닝 트리, 크루스칼 알고리즘.
3. Reorder Routes to Make All Paths Lead to the Capital (LeetCode 1466)
   설명: 모든 경로를 특정 노드로 연결하기 위한 최소 간선 변경을 계산합니다.
   설명: 모든 경로가 도시 0으로 향하도록 최소한의 도로 방향을 변경합니다.
   핵심 개념: 그래프 탐색, DFS, BFS.
4. Find the Shortest Superstring (LeetCode 943)
   설명: 주어진 문자열 배열을 모두 부분 문자열로 포함하는 가장 짧은 문자열을 찾습니다.
   핵심 개념: DP, 비트마스크, 그래프 이론.
   참고: 이 문제는 여행하는 외판원 문제(TSP)의 변형으로 간주될 수 있습니다.

 

택배 운송 경로 문제

1. Parallel Courses (LeetCode 1136)
   설명: 모든 코스를 완료하는 데 필요한 최소 학기 수를 계산합니다.
   핵심 개념: 위상정렬, 그래프 탐색.
2. Delivery Route Optimization (Custom Problem - 구현 필요)
   설명: 주어진 여러 경로에서 최소 시간으로 모든 지점을 방문하는 최적 경로를 찾습니다.
   핵심 개념: 다익스트라, BFS.
3. Optimal Delivery Path (Custom Problem - 구현 필요)
   설명: 여러 배송지의 패키지를 가장 적은 거리로 운반할 경로를 찾습니다.
   핵심 개념: TSP + 제한 조건 추가.
4. Count All Valid Pickup and Delivery Options (LeetCode 1359)
   설명: n개의 주문에 대해 유효한 픽업 및 배송 순서의 모든 가능한 조합을 계산합니다.
   핵심 개념: 조합론, 수학적 계산.
5. Bus Routes (LeetCode 815)
   설명: 주어진 버스 노선에서 최소한의 버스를 타고 목적지에 도달하는 방법을 찾습니다.
   핵심 개념: BFS, 그래프 탐색.

 

공정 설계 문제 등 유사 문제

1. Alien Dictionary (LeetCode 269 - Premium)
   설명: 주어진 단어 목록에서 알파벳의 순서를 결정합니다.
   핵심 개념: 위상정렬, 그래프 탐색.
2. Course Schedule II (LeetCode 210)
   설명: 특정 순서로 코스를 완료하기 위한 순서를 반환합니다.
   핵심 개념: 위상정렬, DFS.
3. Job Scheduling with Dependencies (LeetCode 1235)
   설명: 종속성이 있는 작업을 효율적으로 스케줄링하며 최대 이익을 찾습니다.
   핵심 개념: DP, 그래프.
4. Critical Connections in a Network (LeetCode 1192)
   설명: 단일 연결을 끊으면 네트워크가 분리되는 간선을 찾습니다.
   핵심 개념: 그래프, 타잔 알고리즘.
5. Best Position for a Service Centre (LeetCode 1515)
   설명: 주어진 고객 위치에서 서비스 센터의 최적 위치를 찾아 모든 고객과의 유클리드 거리 합을 최소화합니다.
   핵심 개념: 최적화, 수학적 계산.
6. Number of Ways to Arrive at Destination (LeetCode 1976)
   설명: 목적지에 도달하는 최단 경로의 수를 계산합니다.
   핵심 개념: 다익스트라 알고리즘, 그래프 탐색.