그래프 (2)

1. DAG

DAG는 사이클이 없는 방향성 비순환 그래프를 의미 한다. 해당 그래프는 수학적으로 아주 재밌는 특징들이 많아 해당 경우일 경우 쉽고 빠르게 문제를 해결하는 알고리즘이 존재하며 Dynamic Programming으로도 연되어 사용할 수 있다.

 

1. 위상 정렬

위상 정렬은 DAG를 하나의 정렬 형태로 만들어 낸 것이다. 하나의 DAG그래프에 대해 여러 위상 정렬이 나올 수 있음.

 

위상 정렬을 구하는 방법은 3가지 단계를 통해 이루어 진다.

처음 : 노드가 아직 처리되지 않음
중간 : 노드가 처리되는 중
완료 : 노드의 처리가 모두 끝

 

먼저 모든 노드는 처음 상태에 존재한다. 여기서 임의의 노드하나를 정하면 해당 노드의 이동 가능한 노드로 뻗어나가며 처리를 진행하는데 이 때 처음 노드를 포함한 거쳐가는 모든 vertex가 중간 상태가 되며 여기서 뻗어나간 즉 vertex에서 이동 할 수 있는 노드의 처리가 완료상태면 해당 vertex도 완료상태가 된다.

 

완료상태가 된 노드는 List에 넣어주면 되고 이렇게 임의의 노드를 돌아가며 모든 노드가 완료 상태가 될 때까지 진행하면 된다.

 

그리고 List를 거꾸로 뒤짚으면 바로 위상 정렬이 된다.

 

Ex)

아래와 같은 DAG 그래프가 존재할 때

 

4를 처음 시작 노드로 잡으면

4를 포함 4에서 이동할 수 있는 2,4 vertext가 중간 상태가 된다.

 

여기서 더 이상 갈 곳이 없는 3번 vertex는 완료 상태가 되고 이를 따라서

List = {3} 이된다.

추가적으로 3이 완료 상태가 됨에 따라서

2와 4도 완료 상태가 되고

List = {3,2,4} 가 된다.(4가 2보다 먼저들어가도 상관없음)

 

다음으로 1을 선택해서 진행하게 되면 1이 중가 상태가 되고

1에서 이동할 수 있는 2가 완료상태 이므로 1도 완료상태가 되며

List = {3,2,4,1}이 된다.

 

여기서 리스트를 거꾸로 뒤짚으면 위상정렬 {1,4,2,3} 이 만들어 진다.

 

 

 

1. 동적 계획법

위와 같이 위상 정렬을 만들면 쉽게 동적 계획법을 사용할 수 있다.

A) 노드 a에서 b까지의 최장/최단 경로

B) 서로 다른 경로으 개수

C) 경로 중 간선의길이가 가장 짧은 개수        

D) 모든 경로에 포함된 노드는 어떤 것?

 

위와 같은 문제들이 주어졌을 때 위 위상 정렬을 예를 들어 A(3)의 값을 구한다면

A(2), A(4) 값 중 최적의 값을 구한 뒤 3까지 간선 비용을 더한 값이 A(3)이 된다. 즉 위와 같은 방법으로 Top-Down 형식의 동적 계획법을 만들 수 있다.

 

 

1. 후속 노드 그래프

후속 노드 그래프란 output 차출이 반드시 1인 그래프를 말하며 함수형 그래프라고도 말한다. 또한 후속 노드 그래프는 시작 노드를 기점으로 n번 이동 했을 때 노드의 값을 구하는 succ 함수를 만들어 계산을 진행할 수 있다.

Ex) succ(2,3)

2번 vertex에서 3번 이동했을 때 vertex의 값을 의미 함.

 

Succ의 함수의 재밌는 점은 succ(x,k)를 구할 때

X에서 k만큼 이동한 것이 아닌 2/k만큼 이동한 vertex에서 다시 2/k만큼 이동한 것이 x에서 k만큼 이동한 것과 같으므로

 

Succ = succ(succ(x,k/2),k/2)로 나타낼 수 있다. 이렇게 처리하는 경우 기존 O(n)에서 O(logn)으로 효율적인 알고리즘 운영이 가능하다.

 

 

1. 후속 노드 그래프에서 사이클 찾기 (플로이드-Tortoise and Hare 알고리즘)

후속 노드 그래프의 특징을 이용해서 효율적으로 사이클을 찾을 수 있다.

먼저 시작 노드 x에 대해서 a는 1칸씩 b는 2칸씩 이동한다 그리고 a=b인 시점이 존재한다면 사이클이 존재하는 것이다.

 

여기서 추가적으로 x에서 사이클의 첫 시작점까지의 거리를 찾을 수 있는데 이는 수학적으로 아래와 같다.

 

사이클의 어느 시점에서 a랑 b는 만났을 것이다.

즉 x에서 첫 사이클까지의 거리를 i라고하고 i에서 a와 b가 만난지점까지의 거리가 j라고 하자. 또한 사이클의 이를(k라고하자)

 

즉 a는 i+j만큼 이동한 것이고 b는 i+c*k + j이다.(c는 사이클은 돌은 횟수) 여기서 b는 a의 두배 속도이므로 b= 2*a와 같으므로

2i+2j=i+c*k+j 이다.

식을 정리하면 i=c*k-j이다. 즉 c*k는 원 한바퀴를 의미하므로 원 한바퀴에서 j만큼 못간 거리 즉 현재 위치가 k-j만큼 이동한 거리임을 의미한다.

 

여기서 a는 다시 x로이동해서 1칸씩 이동하고 b는 해당 위치에서 1칸씩 이동한다면 a가 x에서 i만큼 이동하는 동안 b는 이미 사이클 시작점에서 j만큼 이동한 위치에서 시작해 i만큼 즉 k-j만큼을 이동하므로 a와 b가 사이클의 시작점에서 만나게 된다.

 

결과적으로 식을 정리하면

A는 1칸씩 B는 2칸씩 이동하다가 같은 값이 된다면(사이클 존재)

A는 시작 위치로 이동

A는 1칸씩 B는 1칸씩 이동

A와 B가 다시 만나면 해당 위치가 사이클의 시작지점이 된다.