이 프로그램은 C++을 활용해 전기 회로에서 각 부품(컴포넌트)을 연결하는 배선(와이어) 길이를 최소화하는 방법을 다룹니다. 내부적으로는 그래프 이론의 대표적인 최단 경로 알고리즘인 다익스트라(Dijkstra) 알고리즘을 사용하여, 시작 부품으로부터 나머지 모든 부품까지의 최단 거리를 계산합니다.
회로는 인접 행렬 형태의 그래프로 표현되며, 행렬의 각 요소 g[u][v]는 부품 u와 v 사이의 배선 길이(가중치)를 의미합니다. 값이 0이면 두 부품이 직접 연결되어 있지 않음을 뜻합니다.
알고리즘
시작
함수 optimizeLength() :
1) dist[N] 배열을 선언한다.
2) sptSet[i]는 부품 i가 최단 경로 트리에 포함되었거나,
시작점(src)에서 i까지의 최단 거리가 확정된 경우 true가 된다.
3) 모든 거리 값을 INFINITE(무한대)로 초기화하고, sptSet[]은 false로 초기화한다.
4) 시작 부품 자기 자신과의 거리는 항상 0이다.
5) cnt = 0부터 N-2까지 반복하며 모든 부품에 대한 최단 경로를 구한다.
A) 아직 처리되지 않은 부품들 중 최소 거리를 가진 부품을 선택한다.
B) 선택된 부품을 '처리됨'으로 표시한다.
C) 선택된 부품에 인접한 부품들의 dist 값을 갱신한다.
D) dist[v]는 v가 sptSet에 속하지 않고, u에서 v로 가는 간선이 존재하며,
u를 경유하는 src→v 경로의 총 가중치가 현재 dist[v]보다 작을 때만 갱신한다.
끝예제 코드
#include <limits.h>
#include <iostream>
using namespace std;
#define N 6
int minDist(int dist[], bool sptSet[]) { //최소 거리 값을 가진 부품을 찾는 함수
int min = INT_MAX, min_index;
for (int v = 0; v < N; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void displaySolution(int dist[], int n) { //계산 결과를 출력하는 함수
cout << "Component\tDistance from other component\n";
for (int i = 0; i < n; i++)
printf("%d\t\t%d\n", i, dist[i]);
}
void optimizeLength(int g[N][N], int src) { //배선 길이 최적화 수행
int dist[N];
bool sptSet[N];
for (int i = 0; i < N; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
//모든 부품에 대한 최단 경로를 구한다.
for (int cnt = 0; cnt < N - 1; cnt++) {
//아직 처리되지 않은 부품 중 최소 거리 부품을 선택
int u = minDist(dist, sptSet);
//선택된 부품을 처리됨으로 표시
sptSet[u] = true;
//선택된 부품에 인접한 부품들의 dist 값 갱신
for (int v = 0; v < N; v++)
if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v])
//v가 sptSet에 없고, u→v 간선이 존재하며, u를 경유하는 경로의
//총 가중치가 현재 dist[v]보다 작을 때만 dist[v]를 갱신
dist[v] = dist[u] + g[u][v];
}
displaySolution(dist, N);
}
int main() {
int g[N][N] = { { 0, 0, 6, 7, 0, 4}, { 4, 0, 8, 0, 1, 2 },
{0, 9, 0, 2, 0, 4 }, { 0, 0, 7, 0, 9, 5 }, { 0, 1, 0, 0, 6, 7 }, { 6, 7, 0, 0, 2, 3} };
cout << "Enter the starting component: ";
int s;
cin >> s;
optimizeLength(g, s);
return 0;
}실행 결과
Enter the starting component: 4 Component Distance from other component 0 5 1 1 2 9 3 11 4 0 5 3
위 실행 결과에서 시작 부품으로 4를 입력하면, 부품 4에서 나머지 각 부품(0~5)까지의 최단 배선 거리가 순서대로 출력됩니다. 예를 들어 부품 1까지의 최단 배선 길이는 1, 부품 3까지는 11임을 확인할 수 있습니다.
핵심 포인트 정리
- 입력 그래프: 6×6 인접 행렬로 회로의 부품 간 연결 관계와 배선 길이를 표현합니다.
- minDist(): 아직 확정되지 않은 부품 중 가장 가까운 부품의 인덱스를 반환합니다.
- sptSet 배열: 최단 거리가 확정된 부품을 추적하여 중복 계산을 방지합니다.
- 시간 복잡도: 인접 행렬 기반 구현이므로 O(N²)이며, 부품 수가 많아지면 인접 리스트 방식이 더 효율적입니다.
이처럼 다익스트라 알고리즘을 응용하면 PCB 설계나 배선 자동화 등 실제 전기·전자 분야에서 배선 비용과 신호 지연을 줄이는 최적화 문제에 활용할 수 있습니다.