20260421-Prim and Daijkstra: 알고리즘 구현 및 테스트

이번 커밋에서는 두 가지 중요한 그래프 알고리즘인 Prim 알고리즘과 Dijkstra 알고리즘을 구현하고 테스트하는 작업을 진행했습니다. 해당 코드는 Week7_problem 디렉토리 내의 4.1.prim_problem.py와 4.3.dijkstra_problem.py 파일에 포함되어 있습니다. 총 311줄의 코드가 추가되었습니다.

요약

이번 작업은 알고리즘 과제 제출을 위해 Prim 알고리즘과 Dijkstra 알고리즘을 Python으로 구현하고, 제공된 테스트 케이스를 통해 각 알고리즘의 올바른 동작을 검증하는 데 중점을 두었습니다. Prim 알고리즘은 최소 신장 트리(MST)를 생성하고, Dijkstra 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾습니다.

배경 및 목적

알고리즘 수업의 7주차 과제로, 그래프 탐색 및 최단 경로, 최소 신장 트리 관련 알고리즘에 대한 이해도를 높이고 실제 구현 능력을 키우기 위해 이 작업이 필요했습니다. Prim 알고리즘은 연결된 가중치 그래프에서 모든 정점을 최소의 총 간선 가중치로 연결하는 트리를 찾는 데 사용되며, Dijkstra 알고리즘은 음수 가중치가 없는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 계산하는 데 사용됩니다.

구현 내용

1. Week7_problem/4.1.prim_problem.py

이 파일은 Prim 알고리즘을 구현합니다.

• 주요 변경사항: Prim 알고리즘의 핵심 로직을 Python 함수 prim(n, W)로 구현했습니다. 이 함수는 정점의 수 n과 인접 행렬 W를 입력받아 최소 신장 트리를 구성하는 간선들의 리스트 F를 반환합니다.
• 변경 파일: Week7_problem/4.1.prim_problem.py
• 추가 라인: 132
• 삭제 라인: 0
• 핵심 코드 설명:
  • nearest 배열은 현재까지 확정된 정점 집합(Y) 내에서 각 미확정 정점(V-Y)에 가장 가까운 정점을 기록합니다.
  • distance 배열은 현재까지 확정된 정점 집합(Y)과 각 미확정 정점(V-Y) 사이의 최소 거리를 기록합니다.
  • 알고리즘은 n-1번의 반복을 통해 점진적으로 정점을 Y 집합에 추가합니다. 각 반복마다 Y 집합과 가장 가까운 V-Y 집합의 정점(vnear)을 찾아 Y에 편입시키고, 해당 간선을 결과에 추가합니다. 이후 vnear를 기준으로 나머지 V-Y 집합의 정점들과의 거리를 갱신합니다.
  • test_prim_mst 함수는 구현된 prim 함수를 테스트하기 위한 유틸리티 함수입니다. 여러 예제 그래프에 대해 MST를 계산하고 기대 결과와 비교합니다.

2. Week7_problem/4.3.dijkstra_problem.py

이 파일은 Dijkstra 알고리즘을 구현합니다.

• 주요 변경사항: Dijkstra 알고리즘의 핵심 로직을 Python 함수 dijkstra(n, W)로 구현했습니다. 이 함수는 정점의 수 n과 인접 행렬 W를 입력받아 출발점 v1에서 다른 모든 정점까지의 최단 경로를 구성하는 간선들의 리스트 F를 반환합니다.
• 변경 파일: Week7_problem/4.3.dijkstra_problem.py
• 추가 라인: 179
• 삭제 라인: 0
• 핵심 코드 설명:
  • touch 배열은 출발점(v1)에서 특정 정점까지의 현재까지 알려진 최단 경로에서 해당 정점 바로 직전에 오는 정점을 기록합니다.
  • length 배열은 출발점(v1)에서 특정 정점까지의 현재까지 알려진 누적 최단 거리를 기록합니다.
  • 알고리즘은 n-1번의 반복을 통해 출발점에서 가장 가까운 미확정 정점(vnear)을 반복적으로 찾아 확정합니다. vnear가 확정되면, vnear를 경유했을 때 다른 미확정 정점까지의 경로가 더 짧아지는지 확인하고(relaxation), length와 touch 값을 갱신합니다.
  • test_dijkstra_shortest_paths 함수는 구현된 dijkstra 함수를 테스트하기 위한 유틸리티 함수입니다. 여러 예제 그래프에 대해 최단 경로를 계산하고 기대 결과와 비교합니다.

기술적 의사결정

• 데이터 구조: 그래프 표현을 위해 인접 행렬 W를 사용했습니다. 이는 정점 간의 연결 및 가중치를 직관적으로 파악하고 접근하는 데 용이합니다. Prim과 Dijkstra 알고리즘 모두 인접 행렬 기반 구현이 일반적입니다.
• 알고리즘 구현 방식: 두 알고리즘 모두 Greedily하게 최적의 해를 찾아가는 방식으로 구현되었습니다. Prim은 항상 현재 확정된 집합과 가장 가까운 정점을 선택하고, Dijkstra는 항상 출발점에서 가장 가까운 미확정 정점을 선택합니다.

배운 점 및 개선점

• 배운 점:
  • Prim 알고리즘과 Dijkstra 알고리즘의 동작 원리를 코드로 구현하며 깊이 이해할 수 있었습니다. 특히, 각 알고리즘에서 '확정 집합'과 '미확정 집합'을 어떻게 관리하고, 어떤 기준으로 다음 정점을 선택하며, 어떻게 경로/거리를 갱신하는지에 대한 이해가 명확해졌습니다.
  • 인접 행렬을 이용한 그래프 표현과 알고리즘 구현에 익숙해졌습니다.
  • 제공된 테스트 케이스를 활용하여 코드의 정확성을 검증하는 과정의 중요성을 다시 한번 느꼈습니다.
• 개선점:
  • 현재 구현은 모든 테스트 케이스를 통과하지만, 더 큰 규모의 그래프에서는 인접 행렬의 공간 복잡도(O(V^2))가 비효율적일 수 있습니다. 향후 인접 리스트를 사용하거나 우선순위 큐를 도입하여 알고리즘의 시간 복잡도를 개선하는 것을 고려해볼 수 있습니다. (예: Dijkstra의 경우 O(E log V) 또는 O(E + V log V))
  • Prim 알고리즘의 경우 distance 배열을 음수로 설정하여 방문했음을 표시하는 방식 대신, 별도의 visited 집합을 사용하는 것이 더 명확할 수 있습니다.
• 다음 단계 계획:
  • 우선순위 큐를 활용한 Dijkstra 알고리즘 구현을 시도하여 성능 개선을 확인합니다.
  • 그래프 알고리즘에 대한 추가적인 학습 (예: Kruskal 알고리즘, 플로이드-워셜 알고리즘) 및 구현을 진행합니다.

참고 자료

• 수업 강의 자료 (알고리즘 관련)
• 온라인 알고리즘 튜토리얼 (Prim, Dijkstra 알고리즘 설명)