해밀턴 순회 및 경로 문제

해밀턴 순회 문제(모든 정점을 한 번씩 방문하고 다시 시작 정점으로 돌아올 수 있는지를 판단, 가중치 고려하지 않음)
해밀턴 경로 문제(해밀턴 순회와 비슷하지만 시작정점으로 돌아올 필요는 없는 경로)

 

알고리즘 팁

• DFS + 백트래킹: 해밀턴 순회와 경로 문제의 기본. 재귀적으로 경로를 탐색하며 경로가 유효한지 확인.
• DP + 비트마스크: 모든 정점을 방문하는 경로 문제를 효율적으로 해결하는 방법. 특히 가중치가 있는 그래프에서 유용.
• 위상 정렬: DAG에서 해밀턴 경로를 찾는 데 강력한 도구.

 

해밀턴 순회 문제 (Hamiltonian Cycle)

목표: 그래프에서 모든 정점을 한 번씩 방문하고 시작 정점으로 돌아올 수 있는지를 판단합니다.

1. Find Hamiltonian Cycle (Custom Problem - 구현 필요)
   설명: 주어진 그래프에서 해밀턴 순환이 존재하는지 여부를 판단합니다.
   핵심 개념: 백트래킹, DFS.
2. Shortest Path Visiting All Nodes (LeetCode 847)
   설명: 모든 노드를 한 번씩 방문하고 시작 지점으로 돌아오는 최소 거리를 계산합니다.
   핵심 개념: BFS, 비트마스크 DP.
   특징: 가중치를 고려한 변형 문제로, 해밀턴 순회와 유사합니다.
3. Traveling Salesperson Problem (TSP) (Custom Problem - 구현 필요)
   설명: 모든 정점을 방문하고 시작점으로 돌아오는 최소 비용 경로를 찾는 문제.
   핵심 개념: DP, 비트마스크.

 

해밀턴 경로 문제 (Hamiltonian Path)

목표: 모든 정점을 한 번씩 방문하는 경로를 찾습니다. 시작 정점으로 돌아올 필요는 없습니다.

1. All Paths From Source to Target (LeetCode 797)
   설명: 방향성 비순환 그래프(DAG)에서 시작 노드에서 끝 노드까지 모든 경로를 찾습니다.
   핵심 개념: DFS, 백트래킹.
   특징: 그래프가 DAG로 제한되지만, 해밀턴 경로의 기본 구조와 유사합니다.
2. Find Hamiltonian Path (Custom Problem - 구현 필요)
   설명: 주어진 그래프에서 모든 정점을 정확히 한 번씩 방문할 수 있는 경로가 존재하는지 확인합니다.
   핵심 개념: 백트래킹, DFS.
3. Path With Maximum Probability (LeetCode 1514)
   설명: 가중치 그래프에서 최대 확률 경로를 찾습니다.
   핵심 개념: 다익스트라 알고리즘.
   특징: 가중치를 고려한 경로 찾기 문제로, 해밀턴 경로 문제의 변형.
4. Course Schedule (LeetCode 207)
   설명: 방향성 비순환 그래프(DAG)에서 모든 코스를 완료할 수 있는지 확인합니다.
   핵심 개념: 위상 정렬.
   특징: 모든 노드를 방문할 수 있는지 확인하는 점에서 해밀턴 경로와 유사.
5. Longest Path in a Directed Acyclic Graph (Custom Problem - 구현 필요)
   설명: DAG에서 가장 긴 경로를 찾는 문제.
   핵심 개념: DP, 위상 정렬.
6. Reorder Routes to Make All Paths Lead to the City Zero (LeetCode 1466)
   설명: 도로의 방향을 변경하여 모든 경로를 특정 도시로 향하게 만듭니다.
            모든 도로가 특정 도시로 향하도록 방향을 재구성하며, 해밀턴 경로와 유사한 그래프 순회 방식 사용.
   핵심 개념: 그래프 탐색, DFS, BFS.
7. Network Delay Time (LeetCode 743)
   설명: 특정 노드에서 모든 노드로의 경로가 있는지 확인하고, 모든 경로가 존재하는 최소 시간을 계산합니다.
   핵심 개념: 다익스트라 알고리즘, 그래프 탐색.

 

추가 참고: 관련 문제, 유사 문제 및 변형

• Longest Path in a Directed Acyclic Graph (Custom Problem - 구현 필요)
  설명: DAG에서 가장 긴 경로를 찾는 문제.
  핵심 개념: DP, 위상 정렬.
• Find the Shortest Superstring (LeetCode 943)
  설명: 주어진 문자열 배열을 모두 포함하는 가장 짧은 문자열을 찾는 문제로, TSP의 변형.
  핵심 개념: DP, 비트마스크.
• Parallel Courses (LeetCode 1136)
  설명: 모든 과정을 완료하는 데 필요한 최소 학기를 계산.
  핵심 개념: 위상 정렬, 그래프 탐색.
• Critical Connections in a Network (LeetCode 1192)
  설명: 그래프에서 단일 연결이 끊기면 네트워크가 분리되는 간선을 찾습니다.
  핵심 개념: 타잔 알고리즘, 그래프 탐색.
• Pacific Atlantic Water Flow (LeetCode 417)
  설명: 특정 조건에 따라 물이 흐를 수 있는 모든 정점을 찾습니다.
  핵심 개념: DFS, 그래프 탐색.
• Word Search (LeetCode 79)
  설명: 격자에서 특정 단어를 찾을 수 있는 경로를 찾습니다.
  핵심 개념: DFS, 백트래킹.