[내배캠] 본캠 18일차. 그래프 알고리즘, 다익스트라

그래프 알고리즘.
그래프란
정점(vertex)와 간선(edge)로 이루어진 자료구조 , A ---- B 여기서 점은 A,B 간선은 ----
방향 그래프와 무방향 그래프로나뉜다.  방향그래프는 ---> 이렇게 화살표가 존재하고
이쪽방향으로만 갈수있음, 무방향은 ------, 양쪽다 왔다갔다할수있음.
가중치 그래프는 간선에 가중치가 있다.
비유하자면 도로마다 거라(km)나 통행료(cost)를 표시한것

A ---5 ----B 라 하면 A<--->B 사이의 거리가 5
방향 가중치 그래프라면
A-->B(5), B-->A(7) 처럼 서로 다른 값도 가능하다.



그래프 탐색방법에는
3-1 깊이우선탐색 DFS
루트에서 시작해서 가능한 깊이 들어가서 노드를 탐색하고 더이상 방문할 노드가없으면
이전 노드로 돌아가는 방식이다.
3-2 너비우선탐색 BFS 
루트에서 시작하여 가까운 노드부터 방문하고 그 다음 레벨의 노드를 방문하는 방식이다.

두가지 탐색방법이 위와 같이 존재한다.

이를 위한 예제는 아래와 같다.

using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write($"{v} ");

        foreach (int n in adj[v])
        {
            if (!visited[n])
            {
                DFSUtil(n, visited);
            }
        }
    }

    public void BFS(int v)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[v] = true;
        queue.Enqueue(v);

        while (queue.Count > 0)
        {
            int n = queue.Dequeue();
            Console.Write($"{n} ");

            foreach (int m in adj[n])
            {
                if (!visited[m])
                {
                    visited[m] = true;
                    queue.Enqueue(m);
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(6);

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

        Console.WriteLine("DFS traversal:");
        graph.DFS(0);
        Console.WriteLine();

        Console.WriteLine("BFS traversal:");
        graph.BFS(0);
        Console.WriteLine();
    }
}


예제를 하기에 앞서
복습차 메모리영역의 어디에 어떤형태로 무엇이 저장되는지 한번 다시 짚고넘어가자.
우선,
로컬 변수들, 값형태들은 스택영역에 저장된다.
스택에는 메서드가 호출될때 생성되는 지역변수, 매개변수, 리턴 주소등을 저장한다.

그리고  클래스, 컬렉션류들은 참조 형태로 힙영역에 저장된다.
정확히는 런타임에 new를 통한 객체를 생성하면
해당 객체는 힙영역에 할당된다. 해제는 가비지컬렉션 클래스에서 담당한다.
그렇다면 해당 객체를 가리키는 참조 주소 값은 어디에 저장될까?
이는 상황따라 다르다다.
일단, 객체들은 항상 힙에 할당되지만 이를 가리키는 주소들은
지역변수인경우 스택에,
특정 클래스의 필드인경우 해당 클래스를 new해서 만든 객체 인스턴스안에 저장되니 
그 객체 안에 있는 객체를 가르키는 주소 역시 힙영역에
static 필드인경우 
static 메모리 영역에 저장될수 있다.

예를들면
class Dog 를 가지고
Dog dog = new Dog(); 를 program main 함수에서 바로 실행해서 생성한다면
해당 new Dog(); 라는 객체를 가리키는 dog라는 참조값은 스택영역에 로컬변수로서 저장된다.
객체 데이터자체는 힙에 저장되어있지만 말이다.
그리고 참조값이 끊어지면 아무것도 할당안된 해당 객체는 가비지컬렉터에 의해 회수된다.
그렇다면 지역변수가아닌경우를 예를들어보자.
예를들어
특정 클래스 안에 필드값으로 선언된 멤버에 해당 객체 생성을 할당한다면?
public class Kennel
{
 public Dog dog = new Dog();
}

이때 dog필드는 힙위에 생성된 kennel 객체 내부에 저장되니 힙영역에 주소값으로 참조형태로
저장되는것이다.

static인경우도있다

public class Zoo
{
 public static Dog dog = new dog();
}

이 dog 변수는 static 영역에 저장된다.
아까말했지만 필드나 스태틱이아닌 스택에 참조값으로도 저장되는 경우가 있었는데
메서드 내에 지역변수로도 참조값이 들어올수있기때문에
그냥 빈클래스를 메인함수에서 객체생성하는것외에도 이런 형태로도 스택에 참조값으로 저장된다.
void Foo()
{
 List<int> list = new List<int>();
     지역변수  =  객체(힙)
}

....
다시 그래프로 돌아와서 구조를 훑어보자.

준비단계에서 보자면 
Graph라는 클래스에서 우리는 변수 V 맴버가 정의되어있고
List<int> 타입을 가지는 배열 adj도 정의되어있다.

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

그다음에 Graph의 생성자에서는 정수타입으로 v를 받아서
V에 할당하고,
해당 V의 크기로
adj라는 리스트타입의 배열 객체를 생성한뒤,
해당 V 크기만큼 순회하여
adj[i] .... adj[v-1] 인덱스에다 비어있는 리스트 객체들을 하나씩 할당해서넣어준다.

예를들면 v가 6이면
adj (List<int>[] 배열, 길이=6)
index:    0      1      2      3      4      5
value:  List   List   List   List   List   List
        (빈)   (빈)   (빈)   (빈)   (빈)   (빈)
이런식으로 생성되어있는샘이다.

만약에 Graph graph = new Graph(6); 로 Graph 객체를 생성한다면

해당 생성자가 초기화작업을하면서

위와 같은 배열과 배열안의 빈 리스트 객체들을 생성하고 
이 참조값들도 , 객체자체도 전부 힙영역에 저장되어진다.


그리고 AddEdge라는 메서드를 하나 생성하는데, 
파라매터를 보면 인자로 정수값 v와 w를 받고

adj[v]라는 리스트객체에 w값을 넣어준다. 라는 실행코드를 담고있다.


프로그램 메인함수에서
그래프 객체를 생성한다음에 시행한 행동은
이 메서드를 여러번 실행시켜 
adj[v]라는 리스트객체들에게 값들을 할당시켜준것이다.

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

adj[0]: [1,2]
adj[1]: [3]
adj[2]: [3,4]
...

adj (배열, 길이 6)
idx:   0        1         2         3        4        5

       ↓       ↓        ↓        ↓       ↓       ↓
   List[0]    List[1]    List[2]   List[3]  List[4]  List[5]
     [1,2]      [3]      [3,4]      [4,5]     [5]      []

이런식으로 비어있던 리스트객체들은 
각각 값들을 몇가지 가지게되었다.
그런데 그렇다손치더라도 이 리스트의 값들은 말그대로 값형태지
참조형태가 아니니까 다른 리스트나 다른 배열에서 막 참조해서 접근할 수는 없다.
딱 자신의 상위에서만 꺼내볼수있는 상태다.

우리가 하려는것은 이 값들을 참조가 가능한 형태인척 코드로 이어서 꺼내보게 하는것이다.
예를들어 값이었던 List[1]의 3이 
특정 코드에 의해 인덱스 3인것처럼 
List[3]로 연결되게해서 값 4, 5에도 순차적으로 접근가능하게 하는 코드를 만드는것.
이것을 그래프의 논리적인 사고구조라고 할 수 있다.

여기서 깊이우선탐색 DFS의 경우는 위에서 말한 논리사고구조를 행하는 탐색인데
        Console.WriteLine("DFS traversal:");
        graph.DFS(0);
        Console.WriteLine();
요 코드를 메인함수에서 실행하기 전에

우선 graph 클래스에서 해당 DFS라는 메서드를 만들어줄 필요가있다.
이른바, 값들을 인덱스인척 바꿔주는 코드가 필요한것.
우리가 하려는 탐색은 
[0]─→[1]─→[3]─→[4]─→[5]
 │       ↘      ↗
 └─→[2]─→[3]       
요런 탐색을 할것이다. 원래라면 별도로 끊어져있는 리스트 끼리 리스트내부 값을
참조형태인것처럼 바꿔서 순회할 수 있게하는 것이다.

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write($"{v} ");

        foreach (int n in adj[v])
        {
            if (!visited[n])
            {
                DFSUtil(n, visited);
            }
        }
    }

요 두개의 메서드로 가능한데,
먼저 DFS(int v) 메서드의 
int v는 그냥 파라매터만 같은 v로 쓰인거지 아까 graph 객체를 생성할때 넣은 6과는 다른 인자를 받는 창구다.
 위에 보면 코드는 graph.DPS(0)로 썼고 즉 0을 인자로 받았다.
bool[] visited = new bool[V]; 근데 이 메서드안의 V는 자세히보면 대문자다.
이거는 private int V라는 Graph 클래스의 맴버에 할당된 (생성자 호출시에) 6이다.
즉
visited 라는 bool 타입 배열에는 null 값으로 6칸이 만들어졌으며
bool의 기본값은 false이다.
즉 해당 bool [ ] 타입 visited 배열은
index:    0      1      2      3      4      5
value:  false  false false  false  false  false
인상태다.
그리고 그안에서
DFSUtil(v, visited) 라는 함수를 실행한다. 
여기서는 아까 메인함수에서 graph.DPS(0)를 호출했으니
DFSUtil(0, visited)라는 함수를 먼저실행할것이다.


이 DFSUtil 이라는 함수는 실제 탐색용 함수로 파라매터를 보면
int v, bool[] visited 라는 두 인자를 받는다.
앞서 리스트객체를 떠올려보면
adj[0] 에는 [1,2] 가 할당되어있고
adj[1] 에는 [3] 하나가 할당되어있는 상태다.

DFS(0) 호출시 visited = [F,F,F,F,F,F] 이고
호출 DFSUtil(0)의 경우엔 내부로 들어가면
visited[0] = true;
출력은 0
foreach문에서는 adj[0]안의 값들을 하나씩 꺼내보며
첫번째 n= 1일경우
visited[1]은 false 이므로 if문 조건만족해서
DFSUtil(1) 호출 
그안에서
visited[1] = true로 바꿔주고
출력은 1
adj[1] 안에는 뭐가 있는지 꺼내보자면
n=3이므로 
visited[3] = false 이므로 
DFSUtil(3)을 호출
visited[3] = true로 바꿔주고
출력은 3

adj[3] 에대해서 안에 뭐가있는지 또 살펴보고....

이렇게 n을 새로운 v삼아가며 재귀호출하며
visited[n]을 true로 바꿔주고 
출력하고 해당 n을 v삼아 또 재귀호출하고... 
하면서 해당코드를 통해 다음 탐색지점을 찾아나선다.

이걸 도식화해보자면

[0]─→[1]─→[3]─→[4]─→[5]
 │       ↘      ↗
 └─→[2]─→[3] 

이런식으로 말할 수 있고.. 
adj[v] 에 [n₁, n₂, …] 가 있으면
→ “v → n₁, v → n₂, …” 라는 간선 정보 즉,
정점 v가 정점 n과 연결되어있다라고 표현한다.

이를 통해 출력값은
0 1 3 4 5 2 가된다.

우리는 이때 리스트안의 값들을 정점(vertex)이라고 간주하고

간선(Edge)은 숫자값으로의 연결을 기록한다라고 간주한다.
graph.AddEdge(0, 2); //  0번 정점에서 2번 정점으로 가는 간선 추가
메모리상에서는 0번 리스트객체에 2라는 값을 추가한것이지만
이것이 DFS 메서드와 DFSUtil 메서드에 의해 연결점이 되기때문에 한큐에 말해버린것이다.


그다음은 너비우선 탐색 BFS에 대한 부분이다.
마찬가지로
메인 함수에서는
   Console.WriteLine("BFS traversal:");
        graph.BFS(0);
        Console.WriteLine();
로 실행하는데

graph 클래스 위로 올라가보면, 간선을 만드는
AddEdge 메서드까지는 동일하게 사용하나,

public void BFS(int v)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[v] = true;
        queue.Enqueue(v);

        while (queue.Count > 0)
        {
            int n = queue.Dequeue();
            Console.Write($"{n} ");

            foreach (int m in adj[n])
            {
                if (!visited[m])
                {
                    visited[m] = true;
                    queue.Enqueue(m);
                }
            }
        }
    }

라는 메서드가 존재한다.

우선 queue는 선입선출이다. 선입후출이었던 스택과는 구조가 다르다.
먼저 들어가면 dequeue 할때 먼저 나오는것이다.

마찬가지로 visisted라는 타입은 bool 로, 해당 배열은 [f,f,f,f,f,f] 로 만들어져있다.

| 단계 | visited            | queue       | 동작 설명                                           | 출력 순서  |
|:----:|:------------------:|:------------:|:-----------------------------------------------:|:-----------:|
| 초기| [F, F, F, F, F, F]   | []             | 시작 전                                              | (없음)      |
| 1    | [T, F, F, F, F, F]   | [0]           | visited[0]=T, enqueue(0)                         |              |
| 2    | [T, F, F, F, F, F]   | []             | dequeue→n=0, 출력 “0 ”                        | 0           |
|      |                       |               | 이웃 [1,2] 검사: 1,2 모두 미방문 → enqueue |              |
|      | [T, T, T, F, F, F]    | [1,2]        |                                                        |              |
| 3    | [T, T, T, F, F, F]   | [2]           | dequeue→n=1, 출력 “1 ”                        | 0 1         |
|      |                       |               | 이웃 [3]: 미방문 → enqueue(3)                 |              |
|      | [T, T, T, T, F, F]   | [2,3]         |                                                        |              |
| 4    | [T, T, T, T, F, F]   | [3]           | dequeue→n=2, 출력 “2 ”                        | 0 1 2       |
|      |                       |               | 이웃 [3,4]:3은방문, 4는미방문 → enqueue(4) |               |
|      | [T, T, T, T, T, F]   | [3,4]         |                                                        |               |
| 5    | [T, T, T, T, T, F]   | [4]           | dequeue→n=3, 출력 “3 ”                        | 0 1 2 3     |
|      |                       |               | 이웃 [4,5]: 4은 방문, 5 미방문 → enqueue(5) |               |
|      | [T, T, T, T, T, T]   | [4,5]         |                                                        |               |
| 6    | [T, T, T, T, T, T]   | [5]           | dequeue→n=4, 출력 “4 ”                        | 0 1 2 3 4   |
|      |                       |               | 이웃 [5]: 이미 방문 → 스킵                       |               |
| 7    | [T, T, T, T, T, T]   | []            | dequeue→n=5, 출력 “5 ”                         | 0 1 2 3 4 5 |
|      |                        |              | 이웃 [] → 큐 빈 상태 → 종료                     |                |


결과적으로 
출력은 0 1 2 3 4 5 가 나온다...


-------------

최단경로 알고리즘 (굉장히다양함)

1. 다익스트라 알고리즘
하나의 시작정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
음의 가중치를 갖는 간선이 없는 경우 사용한다.

2. 벨만포드 알고리즘
음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘
음수 사이클이 있는 경우에도 탐지가능.

3. A* 알고리즘 (굉장히 많이쓰임)
특정 목적지까지의 최단경로를 찾는 알고리즘
휴리스틱 함수를 사용하여 각 정점까지의 예상비용을 계산하고
가장 낮은 예상비용을 가진 정점을 선택하여 탐색한다.


우선 다익스트라 알고리즘 예제다.
하나의 시작정점에서 다른 모든 정점까지 최단경로를 찾아야한다. 음의가중치는 없어야한다.
그 방법은 시작점으로부터 거리가 가장 가까운 정점을 하나씩 골라서 그 이웃거리를
갱신(완화-relaxation)하는 패턴이다.

우선 쓰는이유는 
가중치가 있는 그래프에서,,
한 정점에서 모든 정점까지의 최단거리를 구해야할때,,
간선 가중치가 0이상이면 O(V^2) 인접행렬 또는 O(E log V)우선순위 큐 안에서해결한다.

복습을해보자.
앞서 그래프란것은 정점과 간선을 가지는 자료구조라고 배웠다.
좀더 설명해보자면
정점이란 데이터의 개별요소 하나하나를 가리킨다.
예: 도시A, 도시 B, 도시 C ... 또는 사람A,사람 B , 사람 C ....

간선이란 정점과 정점을 잇는 연결이다.
예: 도시 A와 도시 B를 잇는 도로, 사람A와 사람 B사이의 친구관계

그래프 = (정점들의 모임) + (정점들을 잇는 간선들의 모임) 
으로 구성되는것인데.

왜쓰는가?
현실 세계의 네트워크 구조를 표현하기 좋다.
지도상의 길찾기, 소셜 네트워크 친구관계, 인터넷 라우팅등..
알고리즘 문제에서 복잡한 연결관계를 효율적으로 다루도록 도와준다.

컴퓨터에는 어떤식으로 저장되는가.
앞서 공부했던 가중치없는 그래프를 예를들어

인접리스트(Adjacency List)
List<int>[] adj = new List<int> [V];
// adj[u] 안에 v가 있으면 u -> v 간선존재한다. 해당 u를 인덱스와해서 v 삼아
탐색했던 DFS를 기억할것이다.

그다음
인접행렬(Adjacency Matrix)

int [ , ] graph = new int [V, V];
// graph[u , v] ! = 0 이면 u -> v 간선 존재, 값이 가중치 라고한다
아직은 뭔소린지 모르겠다.. 내용을 계속해서보자.

우선 이 그래프의 정점과 간선이라는 것은 추상화된 개념이라는것을 확인했다.

실제로는 배열,리스트 같은 실제메모리 구조에 숫자와 컬렉션으로 담아서
컴퓨터가 어느 정점에서 어느 정점으로 이동할 수 있는지 직접 읽고 처리할 수 있도록
하는것이 바로 그래프 자료구조다.

예제를 한번 보자

    class DijkstraExample
    {
        static int V = 6; // 정점의 수

        // 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
        static void Dijkstra(int[,] graph, int start)
        {
            int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
            bool[] visited = new bool[V]; // 방문 여부 배열

            // 거리 배열 초기화
            for (int i = 0; i < V; i++)
            {
                distance[i] = int.MaxValue;
            }

            distance[start] = 0; // 시작 정점의 거리는 0

            // 모든 정점을 방문할 때까지 반복
            for (int count = 0; count < V - 1; count++)
            {
                // 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
                int minDistance = int.MaxValue;
                int minIndex = -1;

                for (int v = 0; v < V; v++)
                {
                    if (!visited[v] && distance[v] <= minDistance)
                    {
                        minDistance = distance[v];
                        minIndex = v;
                    }
                }

                // 최소 거리를 가진 정점을 방문 처리
                visited[minIndex] = true;

                // 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
                for (int v = 0; v < V; v++)
                {
                    if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
                    {
                        distance[v] = distance[minIndex] + graph[minIndex, v];
                    }
                }
            }

            // 최단 경로 출력
            Console.WriteLine("정점\t거리");
            for (int i = 0; i < V; i++)
            {
                Console.WriteLine($"{i}\t{distance[i]}");
            }
        }

        static void Main(string[] args)
        {
            int[,] graph = {
            { 0, 4, 0, 0, 0, 0 },
            { 4, 0, 8, 0, 0, 0 },
            { 0, 8, 0, 7, 0, 4 },
            { 0, 0, 7, 0, 9, 14 },
            { 0, 0, 0, 9, 0, 10 },
            { 0, 0, 4, 14, 10, 0 }
        };

            int start = 0; // 시작 정점

            Dijkstra(graph, start);
        }
    }

해당 예제를 이해하기전에
우선 반복문과 불변식에대해서 공부해보자..

반복문은
for, while, foreach 뭐 이런것들이있다.

while( cond) 의경우 괄호안 조건이 참인동안 계속 스코프내용을 반복한다.
for문도 (초기화; 조건 ; 증감) 으로 이루어져있으며
해당 조건을 성립할때까지 증감하는 반복문이다.

foreach도 해당 컬렉션내를 전부 순회하는 반복문으로,, 그 condition자체가
while루프와 같다. 내부적으로 IEnumerator를 돌리는
while( MoveNext()) 라는 조건을 성립한다고 여겨지기 때문.

불변식은 조건이랑 관계가있어보이지만 조금 다르다.
조건이라는 것은 언제까지 반복을 돌릴지, 언제 멈출지 결정하는 역할을했다.
스코프 내의 코드를 실행하게 만드는 가드역할이다.

그런데 불변식(Loop Invariant)는
매 반복마다, 반복문이 실행되기전(조건 검사직전)에 항상 참이어야하는 논리적 약속을 뜻한다.
무슨말이냐면,
반복문이 제대로 작동하고있는지 보증하기 위한 검사포인트들을 말하는것이다.
for (int i = 0; i < n; i++)에서 
i< n 이라는 조건이 있다면 이것은 반복을 돌릴지 말지를 정하는것이고
이것과 무관하게
불변식은 지금 이순간 (조건 검사직전)에 상태가 계속 동일하게 나오고있나? 를 항상 묻는것이다.
다시 정리해보자면,,
불변식:
불변식이란 루프의 "언제"(시작, 중간, 끝) 에도 깨지지않아야하는 상태를 뜻한다.
반복문이있다면 불변식이 등장한다고보면 좋다.
루프자체가 어떤상태를 유지하면서 목표를 이뤄내는지 증명할때 쓰는 개념적 도구이다.
모든 알고리즘에 반드시 명시적인 불변식이 필요한것은 아니지만,(직관적인 루프나 라이브러리
함수 사용시에는 굳이 필요없음)

복잡한 루프나 재귀에서 "이 변수는 언제나 이 의미를 갖는다" 라는 약속을 세우고
그 약속을 깨트리지 않도록 초기화해주고,, 중간에 계속 유지해주고... 완결단계까지 지켜주는것이
알고리즘의 정확성을 보장해준다.
뿐만아니라 명제가 참인상태를 유지하려는 구조덕분에
 코드 이해도, 유지보수성을 향상시키기도한다.


루프 불변식(loop invariant)는 문법(while/for/foreach)에 구애받지않고
어떤 반복이건 그 루프가 돌기 전,중간, 후반에 항상 참이어야하는 별개의 조건이다.
즉,
루프가 한번도 실행되지않았을때도 --> 한번 실행 --> 두번 실행 --> .... -> 루프가 끝났을때
까지 언제나 참이어야하는 논리적 약속이다.

정리:
반복문의 조건 = 제어문 : “얼마나 돌릴까?”

루프 불변식 = 논리적 보증문 : “반복 중간중간에도 이 “약속”은 절대 깨지면 안 된다!”

그렇다면 불변성은 언제 깨지나?
본문에서 그 논리식을 지키지 못하는 코드가 실행될때
증감식이나 조건에서 인덱스를 잘못 다루는 실수를 할때 
주로 발생한다.

우선 불변성이 뭔지 해당 예제를 보자

int[] a = {2, 4, 6, 8};
int sum = 0;

for (int i = 0; i < a.Length; i++)
{
    sum += a[i];
}

여기서 불변식은 뭘까?
조건을 검사하기 직전에 어떤 상태인지 식으로 써보면 된다.
int i = 0으로 초기화 하기전에
sum = 0이다. 
int i = 0으로 초기화 후에도
i< a.Length라는 조건을 검사하기전에는
sum = 0이다
조건 검사후에야
sum += a[i]를 시행하므로 i가 0일때 조건검사전이라면
sum += a[i];를 시행하기전이니 
처음에 할당한 sum= 0인 상태

그리고 i를 1 증감하면
다시 조건 검사전으로 돌아가는데
한번 실행코드를 통해 시행한 상태일테니, 
sum = sum + a[0] 
즉 
sum = 0 + 2 해서 2가 된다.

조건 검사전을 기준으로 보자면,
i가 초기화 되기전, i가 0일때 sum = 0이었고 , i가 1일때 sum = 2였다.
이것은 ++에 의해 증가하여 i == a.Length 가 되어 조건을 성립하지않을때까지 반복될것이다.
sum = a[0] +  a[1] + ... a[i-1] 이라는 조건전 불변식이 생겼고
이것은 매번 성립한다..( i가 0일때는 0부터~i-1 까지 더하라는 수학적의미에서 유효한게없으니
그냥 빈 합이고 빈합의 값은 0으로 정의된다. 0부터시작해서 -1까지의 항은 없다.)

중간검사와 완료시점 검사도 가능한데,
바로 i < a.Length 검사전 증감이 이루어졌다면
코드실행전에 검사하는게 중간검사..이고 여기서는 계속해서 성립중이다.

완료시점의경우
루프종료후, 
i==a.Length 되는 시점에서 반복문 조건이 깨지니까
for블록을 빠져나온 직후
불변식 + 종료조건(반복문 깨지는조건) i == a. Length를 합쳐서 생각해봤을때

sum == a[0] + … + a[a.Length-1]
이거는 sum = a[0] +  a[1] + ... a[i-1]와 같으니까 불변식은 깨지지않았다고 여기는것이다.

// 잘못된 예
for (int i = 0; i < a.Length; i++)
{
    sum += a[i+1];  // ← 의도는 a[i] 더하기였는데, a[i+1]을 더해 버리면…
}

i = 0 일 때 헤더 불변식(sum == a[0..-1] = 0) 은 여전히 맞지만,

본문에서 sum += a[1] 을 했으므로 sum == a[1] 이 되고,

i++ 후 헤더(i = 1) 진입 시 검사해야 할 불변식은

 a[0..(1−1)]=a[0]
이지만, 실제 sum == a[1] 이어서 불변식이 깨집니다.


------------------
이제 다익스트라 알고리즘에대해서 다시한번 확인해보자.
다익스트라 알고리즘이란,
그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다.
그래프방향의 유무는 상관없이 음수사이클만 존재안한다면 쓸수있다.
실질적 이용에는
가능한 적은 비용으로 가장 빠르게 해답에 도달하는 대부분의 문제에 응용된다.


불변식: 반복문이 돌기 전, 중, 후 언제나

S = {방문(확정)된 정점들의 집합} 을 기준으로

distance[v] = 
  “시작점 s에서 v까지의,  
   경로의 모든 중간 정점이 S에만 속하는 경로들 중  
   가장 짧은 거리”  
또는  
  “아직 그런 경로를 못 찾았으면 ∞”

이 조건은 불변식으로 항상 참이어야한다로 약속하고 들어간다.
여기서 중간정점이란 시작점과 끝점(v)를 제외한 경로상의 모든 정점을 뜻한다.

먼저,
static int V = 6; // 정점의 수
그래프에 총 6개의 정점이 있다는 뜻이다.
이 V를 바꾸면 distance[]와 visited[] 배열의 크기, 그리고 반복회수등이 모두 자동으로 달라진다.

static void Dijkstra(int[,] graph, int start)
{
여기서 인자값으로 받는
graph는 인접행렬로 graph[u,v]에 0이 아닌값이 들어가있으면
정점 u -> 정점 v까지 간선이 있으며 그 사이 가중치는 값이라는 의미다.
비유하자면 도시 u 와 도시 v 사이의 도로의 길이가 값이 될수있다.
이또한 추상적인 약속이며 다차원배열인 [,] 를 이용해서 6개의 정점을 넣어서
u,v를 도착지점으로 이용할
6행 6열 짜리 배열 그래프를 만들예정이다.

start는 출발정점을 넣기로 했다. 여기선 V가 6이므로 0~5중 하나일것이다.

int[] distance = new int[V];    // 시작 정점으로부터의 거리 배열
합에 6칸짜리 정수배열
distance[0] ... distance[5] 를 만들고
distance[i]란 출발점 -> 정점 i 까지의 (현재까지 알려진) 최단 거리를 저장할 예정이다.
현재는 비어있는 상태의 배열이고 우리는 불변식 조건을 부여할 예정이다.

bool[] visited  = new bool[V];  // 방문 여부 배열
6칸짜리 불리언 배열로
기본값인 false가 6개 들어가있다.
visited = [F, F, F, F, F, F]
visited[i] == true 가 되는 순간 정점 i에 방문했고, i까지의 최단거리가 확정되어 더이상
바뀌지않을것이다 라는 용도로 쓰일 예정이다.

    // 거리 배열 초기화
    for (int i = 0; i < V; i++)
    {
        distance[i] = int.MaxValue;
    }
모든 정점까지의 거리를 무한대 혹은 21억(최대값)로 설정하였고 
이는 불변식 아직 방문하지않은경우 그 최단거리를 모른다 상태인것이다.
전체 증감식을 돌려보면

distance = [∞,∞,∞,∞,∞,∞] 상태인셈

아직 최단거리를 아무것도모르는상태다.

    distance[start] = 0; // 시작 정점의 거리는 0
출발점 인자값 int start를 받아서 
start 인덱스에서의 거리는 0이라고 초기화해줬다.
V가 6이었고 0인덱스에서 시작하니
distance[0] = 0 이다.
이상태로 우선 아무것도 안한 상태라면,, 불변식을 성립하고있다.
시작점에서 시작점 즉, 
나자신과의 최단거리는 그냥 0이고,, 방문안했다면 거리가 무한대인상태니까.
distance = [0, ∞, ∞, ∞, ∞, ∞]
distance[0] = 0
visited = [F, F, F, F, F, F]


다음으로 나아가보자.
    // 모든 정점을 방문할 때까지 반복
    for (int count = 0; count < V - 1; count++)
    {
총 V-1회 반복하는데 (V개의 정점들 중 시작점은 이미 정해졌으니 빼버리고)
 매 회마다 아직 확정되지않은 정점 중하나를 꺼낼것이고
그 정점의 최단거리를 확정해주고, 이웃 정점들의 distance[]를 갱신할 예정이다.
0번째 카운트부터
그 내부를 뜯어보면, 우선 
        // 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
        int minDistance = int.MaxValue;
        int minIndex    = -1;

        for (int v = 0; v < V; v++)
        {
            if (!visited[v] && distance[v] <= minDistance)
            {
                minDistance = distance[v];
                minIndex    = v;
            }
        }

minDistance를 무한대로 초기화
minIndex를 -1로 초기화했다.

그다음 for문에서 
for( v = 0...5) 까지 돌면서
!visited[v] 아직 방문안한 정점만
distance[v] <= minDistance : 시작지점인 0부터 v까지의 거리가 지금까지 찾은 최소거리보다 작거나 같으면

내부를 업데이트해주는데,
minDistance = distance[v]
minIndex = v 로 업데이트해준다.

우선 count가 0일때는
minDistance = distance[0]은 0
minIndex = 0인상태다.
첫번째 for문은 distance[v]가 <= 0인 조건을 만족하지못하니까 나머지
v값들에 대해서는 순회를 돌면서 실행하지않고 그냥나온다.

이 한번의 반복이 끝나면
minIndex에 가장 작은 distance 값을 가진 정점번호가 들어있다.

        // 최소 거리를 가진 정점을 방문 처리
        visited[minIndex] = true;
minIndex 정점까지의 최단거리는 이제 완전히 확정된셈이니
visited[minIndex] 를 true로 표시해준다.

        // 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
        for (int v = 0; v < V; v++)
        {
            if (!visited[v] 
                && graph[minIndex, v] != 0 
                && distance[minIndex] != int.MaxValue 
                && distance[minIndex] + graph[minIndex, v] < distance[v])
            {
                distance[v] = distance[minIndex] + graph[minIndex, v];
            }
        }

for(v= 0...5) : 모든 정점 v에 대해서
아직도 확정안됐고 ( !visited[v])
minIndex -> v 간선이있고 (graph[minIndex,v] != 0)
minIndex까지의 거리가 무한이아니며
새경로 (distance[minIndex] + graph[minIndex,v] 가 기존 distance[v] 보다 짧을경우에

완화(releaxtion) 라는것을해준다.
이제부터
distance[v] = distance[minIndex] + graph[minIndex,v]; 라고 말이다.
이렇게하면
지금까지 distance[v] 는 S(확정된 정점집합)을 통과하는 가장 짧은경로만을 허용한다는
불변식이 계속 유지가된다.
Count가 0인동안에 무한대보다 대부분 거리가 짧을테니까?
스타트 정점에서 간선이 있는 모든 정점들과의 distance[v]가 한번 정해진다.
참고로 프로그램 메인함수에 생성한 graph 인스턴스 내용은 아래와같다.
 int[,] graph = {
        { 0, 4, 0, 0,  0,  0 },
        { 4, 0, 8, 0,  0,  0 },
        { 0, 8, 0, 7,  0,  4 },
        { 0, 0, 7, 0,  9,  14},
        { 0, 0, 0, 9,  0,  10},
        { 0, 0, 4,14, 10,  0 }
    };
count 0일때 간선이 있는것은 0행 1열과 1행 0열의 4라는 값이다.
[0,1] = 4 , [1,0] = 4  아까의 추상적인 약속인 [u,v] = value 에 대입해서 생각해보면
0에서 시작해서 1 정점까지의 거리가 4고 ,  1 정점에서 시작해서 0정점까지의 거리도 4니까
간선(도시간 도로)으로 이어져있다라는 추상적 개념으로 받아들일 수 있다. 
따라서 count =0인 시점에서는 
distance = [0, 4, ∞, ∞, ∞, ∞]
visited  = [T, F, F, F, F, F]
으로 된다.

이번에도 중요한점은 힙에 6행6열로 36개의 int칸이 연속적으로 생겼고
바로 이 분리되어 각각의 칸에 별도의 메모리 오프셋에 저장되어있는 값들이 본래라면
서로 간섭할 수 없지만. 코드구현을통해
 정점간 간선으로서의 역할을 할 수 있도록 만드는게 중요하다.

2단계로 돌때(count = 1)일때는
미확정 중 최소 거리 정점 → minIndex = 1 (distance[1]=4)
visited[1] = T 상태이며
따라서 조건에서 visited[2] 단계에서 모든 조건들을 체크해봐서
완화를 해보면
1행 2열과 2행 1열은 8이고 즉,
[1,2] [2,1] 의 거리가 8인 상태다. 
distance[1] + graph[1,2]  < distance[2] (사실상 무한상태)
니까 
4+ 8 < ∞ 로 마지막 조건까지 성립함
그래서 distance[2] = 12로 완화해줌.

distance = [0, 4, 12, ∞, ∞, ∞]
visited  = [T, T, F, F, F, F]

이렇게 반복해서.....

V-1 번 반복이 끝난 시점엔 , 사실상 모든 정점이 확정된다.

    // 최단 경로 출력
    Console.WriteLine("정점\t거리");
    for (int i = 0; i < V; i++)
    {
        Console.WriteLine($"{i}\t{distance[i]}");
    }
}
이제 이걸 출력해주면되고...

실행 하는 메인함수내에서는

static void Main(string[] args)
{
    int[,] graph = {
        { 0, 4, 0, 0,  0,  0 },
        { 4, 0, 8, 0,  0,  0 },
        { 0, 8, 0, 7,  0,  4 },
        { 0, 0, 7, 0,  9,  14},
        { 0, 0, 0, 9,  0,  10},
        { 0, 0, 4,14, 10,  0 }
    };
    int start = 0; // 시작 정점
    Dijkstra(graph, start);
}
그래프의 구체적인 가중치들과,
시작정점의 인덱스를 할당해주고

해당 클래스의 메서드를 두개의 인자값을 받아 실행시키면 출력이되며
최단거리를 찾아준다.

정점 0 → 거리  0
정점 1 → 거리  4
정점 2 → 거리 12
정점 3 → 거리 19
정점 4 → 거리 26
정점 5 → 거리 16

정점5는 왜 16인지도 잠시 그래프를 보면 답이나오는데
2행5열의 값 4와 5행2열의 값 4가 간선(도로)가 되서 연결해주기때문에 최단코스로 
0행 1열 -> 1행0열 -> 1행 2열 -> 2행 1열 -> 2행 5열 -> 5행 2열까지 
총 4 + 8 + 4 의 거리로 이동했기때문이다.
즉 시작점부터 정점 5까지 이동에는 최단거리 16에 순회가능한셈이다.

이 알고리즘을 보면알겠지만
컴퓨터는 특정 논리를 해석하진않는다.
그냥 값을 읽고 비교연산을 수행하고 대입연산을 기계어로 실행할 뿐이다.
이 숫자가 가중치고, 간선이고 그래프의 해당 행과 열이 정점이다 라는 약속은 전혀 모른다.
다만 우리가 추상화하여서 컴퓨터 계산에 이용했을뿐이다.


                    if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
                    {
                        distance[v] = distance[minIndex] + graph[minIndex, v];
                    }
이렇게 완화하는 갱신작업도
뜯어보면 minIndex 값이 갱신되고, bool 값으로 진입조건을 검사해서
방문하지않았다면 시행되고, 그밖의 조건들 검사
계속해서 minIndex 에 해당하는 갱신되는 값에 새로운 그래프 행,열 의 값을 더해주고있을뿐이다.
그러나 우리는 그것을 정점간의 거리로 해석하고 가중치를 둬서 이동하고있다고 여겨지게
논리구조를 짰을뿐이다.

여기서 한번더 나아가 휴리스틱 함수를 이용해서
시작점과 목적지까지의 최단경로를 구할수있는 알고리즘도 존재한다.
해당 A*라는 알고리즘은 아래의 링크에서 잘 설명해주고있다.
http://www.gisdeveloper.co.kr/?p=3897