알고리즘 강좌 6회

- 그리디 #2 -

 

 

5. 그리디의 실제 #3

이번에도 그리디를 이용해서 효과적으로 풀 수 있는 문제를 알아보자.

그래프 G가 있을때, 한 정점에서 다른 모든 정점으로 가는 경로를 구하는 알고리즘을 아는가? 이것은 Dijkstra(다익스트라)라고들 부르는 방법이다. 이 알고리즘은 그래프가 있을때 두 정점사이의 최단거리를 구할때 꽤나 유용하다.

서론은 이 정도로 하고, 본격적으로 이 알고리즘을 알아보자.

다익스트라 알고리즘은 지난회에서 배웠던 MST와 좀 비슷하다. 다음과 같은 그래프(저번에 나왔던)을 보자.

 

A에서 다른 정점으로 가는 최단 경로들을 구해보자.

일단 A를 선택한다. 그리고 A를 집합 Y에 넣는다.

그다음 A에서 가장 가까운 정점 B를 선택하고, B를 집합 Y에 넣는다. 그러면 Y = {A, B}다.

 

그리고 이제부터는 A에서 집합 Y의 부분인 정점을 거쳐서 갈 수 있는 가장 가까운 정점을 잡으면 된다. 즉 이때는 C를 선택하는데, A에서 Y의 부분을 거치는(Y의 부분집합중에는 공집합도 들어감을 주의하라! A에서 바로 갈 수도 있다.) 가까운 C정점을 선택한다. 그러면 Y = {A, B, C}가 된다.

같은 과정을 반복한다. 다음에는 A에서 출발해 Y의 부분인 C정점을 지나 E로 가는 것이 거리 5로 최소경로이므로 E를 선택하면 된다. Y = {A, B, C, E}이다. 이제는 D로 가는게 최단 경로(거리는 7) 이므로 Y= {A, B, C, E, D}이다. 모든 경로까지의 거리를 계산했으므로 알고리즘은 여기서 끝.

각각의 과정에서 경로의 거리를 저장해 두면 알고리즘이 끝난 후 A에서 각 정점까지의 최단경로를 모조리 구할 수 있다.

 

역시 소스를 보면 이해가 쉬울 것이다.

program ____Dijkstra____;

const

n=5;{정점의 개수}

start = 1;{출발하는 정점}

 

{그래프의 상태에 대한 데이터.

D[i,j]<>0 이면 정점i와 정점j간의 거리는 D[i,j]이고,

D[i,j]=0 이면 정점i와 정점j을 연결하는 이음선이 없다는 뜻}

D : array[1..n,1..n] of integer =(

(0,1,3,0,0),

(1,0,3,6,0),

(3,3,0,4,2),

(0,6,4,0,5),

(0,0,2,5,0)

);

 

var

i, j : integer;

min,minp : integer;

L : array[1..n] of integer;{출발하는 정점으로부터 i정점까지의 거리}

Y : array[1..n] of boolean;{집합 Y. 정점 i가 Y에 속하면 Y[i]=true}

 

begin

for i:=1 to n do

if D[start,i]<>0 then L[i]:=D[start,i] else L[i]:=maxint;

L[start]:=0;

Y[start]:=true;{출발정점을 Y에 넣는다}

 

for i:=1 to n do begin

 

min:=maxint;

for j:=1 to n do begin

if (min>L[j]) and (Y[j]=false) and (L[j]<>0) then begin

min:=L[j];

minp:=j;

end;

end;

 

if min=maxint then begin

{중간에 더 연결할 정점이 없다면 그래프가 중간에 끊긴경우}

writeln('Unconnected!');

exit;

end;

 

Y[minp] :=true;{minp정점을 Y에 추가}

for j:=1 to n do begin

{minp정점을 거쳐 갈 수 있는 정점까지의 경로를 저장}

if (D[minp,j]<>0) and (L[j] > L[minp] + D[minp,j]) then

L[j]:=L[minp] + D[minp,j];

end;

 

end;

 

end.

 

위에서 설명한것과는 약간 다르다. 설명한 그대로 코딩을 하면 상당히 복잡해진다-_-; 그래서 그런것이니 이해해 달라.(설명한 그대로 하면 시간복잡도가 늘어나서 O(n^3)이 되버린다)

 

 

5. 정리

대강 엉성하게 나마 그리디 알고리즘에 대해 알아보았다. 그리디 알고리즘은 간단한 만큼 그 쓰임이 아주 많지는 않다. 하지만 위와 같은 문제들에 대해서는 아주 쓸만하고 간단한데다 속도도 빠르다. 게다가 조금 응용하면 근사해를 구하는 문제에도 적용해서 좋은 결과를 얻어낼 수 있다. 그리디를 잘 알아두면 여러가지로 쓸모가 많을 것이다. 다만 항상 주의할 것은, 그리디로 풀어서 만들어낸 해가 항상 전체의 최적해인지 생각해 보아야 하는 것이다.