Develop & Dream

https://leetcode.com/problems/validate-ip-address/

LeetCode 문제를 풀었는데 처음으로 Runtime이 100%만큼의 축적된 다른 답안들 보다 빠르다고 나옴 

신기해서 자세히 보니

총 73,968 명이 답을 했는데 그중에 C++ 만 대략 50~80명 낸듯;;

메모리는 92.27% 답안들 보다 덜 쓴다고 나옴

사실 내 답안이 제일 하위권에 속할 줄 알았는데 의외의 결과 였음

그래도 실력이 향상됐다는 기록이기도 해서 올려봄

코드

class Solution {
public:
    bool IsValidInteger(char *_str)
    {
        if (atoi(_str) > 255)
        {
            return false;
        }
        
        if (_str[0] == '0' && strlen(_str) > 1)
        {
            return false;
        }

        for (int i = 0; i < strlen(_str); i++)
        {
            char c = _str[i];
            if (c >= '0' && c <= '9')
            {
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }

    bool IsValidHexadecimal(char* _str)
    {
        if (_str[0] == '0' && strlen(_str) > 4 )
        {
            return false;
        }

        if (strlen(_str) > 4)
        {
            return false;
        }

        for (int i = 0; i < strlen(_str); i++)
        {
            char c = _str[i];
            bool InValidtest1 = c < '0' || c > '9';
            
            if (InValidtest1)
            {
                bool InValidtest2 = (c < 'a' || c > 'f'); // c가 'a' 보다 작거나, 'f' 보다 크다
                bool InValidtest3 = (c < 'A' || c > 'F'); // c가 'A' 보다 작거나, 'F' 보다 크다
                if (InValidtest2 && InValidtest3)
                {
                    return false;
                }
            }
        }
        return true;
    }

    string validIPAddress(string IP) {
        
        bool validIPv4 = true;
        bool validIPv6 = true;

      
        //1.IPv4 모양인지 아니면 IPv6 모양인지 검사
        //최대 갯수 넘어가는지 검사
        if (IP.length() > 15 || IP.length() < 7)
        {
            validIPv4 = false;
        }

        if (IP.length() > 39 || IP.length() < 15)
        {
            validIPv6 = false;
            if (!validIPv4)
            {
                return "Neither";
            }
        }

        // . 갯수 검사
        size_t tokenCount = 0;
        for (size_t i = 0; i < IP.length(); i++)
        {
            if (IP.c_str()[i] == '.')
            {
                tokenCount++;
            }
        }
        if (tokenCount != 3)
        {
            validIPv4 = false;
        }


        // : 갯수 검사
        tokenCount = 0;
        for (size_t i = 0; i < IP.length(); i++)
        {
            if (IP.c_str()[i] == ':')
            {
                tokenCount++;
            }
        }
        if (tokenCount != 7)
        {
            validIPv6 = false;
        }

        int chunkCount = 0;
        if (validIPv4)
        {
            char IPv4[16] = { 0 };
            strcpy(IPv4, IP.c_str());
            char* tok = strtok(IPv4, ".");
            chunkCount++;
            while (tok != nullptr)
            {
                if (IsValidInteger(tok) == false)
                {
                    validIPv4 = false;
                    break;
                }
                else
                {
                    tok = strtok(NULL, ".");
                    if (tok)
                    {
                        chunkCount++;
                    }
                }
            }
            if (chunkCount != 4)
            {
                validIPv4 = false;
            }
        }
        else if (validIPv6)
        {
            char IPv6[40] = { 0 };
            strcpy(IPv6, IP.c_str());
            int chunkCount = 0;
            char* tok = strtok(IPv6, ":");
            chunkCount++;
            while (tok != nullptr)
            {
                if (IsValidHexadecimal(tok) == false)
                {
                    validIPv6 = false;
                    break;
                }
                else
                {         
                    tok = strtok(NULL, ":");
                    if (tok)
                    {
                        chunkCount++;
                    }
                }
            }
            if (chunkCount != 8)
            {
                validIPv6 = false;
            }
        }

        if (validIPv4)
        {
            return "IPv4";
        }
        else if (validIPv6)
        {
            return "IPv6";
        }
        else
        {
            return "Neither";
        }
    }
};

• 모든 정점에서 모든정점으로의 최단경로를 구할때 사용
• 경유지(거쳐가는 정점)를 기준으로 최단거리를 구함
• 다이나믹 프로그래밍(큰 문제를 작은 문제들로 나눠서 해결)을 보여줌

자료출처:https://blog.naver.com/ndb796/221234427842

아래의 표는 위그래프를 기준으로 출발지에서 목적지까지의 최소 비용을 구한 것이다, 화살표가 목적지로 정방향으로 가리키지 않거나, 중간에 경유지를 거쳐야 하는 경우(예 2 -> 4)들은 무한(값이 있긴한데 정확히 얼마나 되는지 몰라서 무수히 많은 값)으로 추정한다

따라서 위 그래프를 읽으려면, 1에서 2까지 가는 최소 비용은 5 이고

1에서 3까지 가는 비용은 화살표가 1->3 으로 나와있지 않으므로 무한이고

1에서 1 또는 2에서 2 등등 자기 자신을 향하는 경우 비용이 들지 않으므로 모두 0이다 

플로이드 와샬 알고리즘은 모든 정점을 각각 경유지(거쳐가는 정점)로 봤을때 나올 수 있는 최소비용들을 구해서

표를 갱신해 나가는 것이다

이때 이공식이 사용된다

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 + 경유지 에서 Y로 가는 비용

즉, 거쳐가는 정점을 1번부터 시작해서 4번까지 바꿔가면서, 각각의 경유지(거쳐가는 정점)마다

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한뒤 최소비용을 위의 공식에 맞춰서 갱신해 나가는 것이다 일단 1번부터 거쳐가는 정점이라고 한다면

최소비용을 갱신해야될 부분은 아래의 노란부분과 같다

위의 표의 노란부분은 

자기 자신으로 가는 경우는 제외

출발지 또는 목적지가 경유지인 경우도 제외(출발지가 목적지가 경유지인 경우, 경유하는게 아니므로)

한 나머지들이며 갱신해야될 부분이다

2->3 으로 가는 최소비용은 9인데 

경유지는 1이다

X에서 Y로가는 최소비용 vs X에서 '경유지'로 가는 비용 +'경유지'  에서 Y로 가는 비용

위의 공식을 대입 시키면

2에서 3으로 가는 최소비용 vs 2에서 1로 가는 비용 + 1에서 3으로 가는 비용

이 된다, 그대로 표를 보고 대입하면

9 vs 7 + 무한

이 된다 여기서 7+ 무한은 값이 확실하지 않으므로 결국 무한으로 추정하고

9와 비교했을때 9가 더 적다고 판단하여 9를 내버려둔다

이런식으로 갱신해 나가면 아래와 같이 된다

여기서 3->2로 가는 값이 무한에서 7로 바뀐걸 알 수 있다

3 -> 2 로 가는 비용 > (3 -> 1) + (1 -> 2)

무한 > 2 + 5

이므로 2+5 가 무한보다 적으므로, 즉 7로 바뀌었다

그뒤 1을 거치는 표를 기준으로 경유지를 1에서 2로 바꾸고 다시 갱신해준다

아래와 같을 것이다

이런식으로 계속 경유지를 바꿔가며 표를 갱신하면된다

경유지가 마지막 정점인 4인경우 표가 다 완성된다

코드

#include <iostream>

int number = 4;
int INF = 100000000;

// 자료 배열을 초기화
int a[4][4] =
{
	{0, 5, INF, 8},
	{7, 0,	9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};


void floydWarshall()
{
	int oldCost = 0;
	int newCost = 0;
	
	// 결과 그래프를 초기화
	//X에서 Y로가는 최소비용 VS X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
	for (int stopover = 0; stopover < number; stopover++) //stopover : 경유지, 거쳐가는 노드
	{
		for (int start = 0; start < number; start++)
		{
			for (int goal = 0; goal < number; goal++)
			{
				if (stopover < number&& start != goal && start != stopover && goal != stopover)
				{
					oldCost = a[start][goal]; //X에서 Y로가는 최소비용

					//X에서 '거쳐가는노드'로 가는 비용 + 노드1 에서 Y로 가는 비용
					newCost = a[start][stopover] + a[stopover][goal]; 
					
					//둘중에 더 적은 비용을 넣기
					a[start][goal] = oldCost > newCost ? newCost : oldCost; 
				}
			}
		}
	}
}

void PrintGraph(int (*_a)[4])
{
	for (int start = 0; start < number; start++)
	{
		for (int goal = 0; goal < number; goal++)
		{
			if (a[start][goal] == INF)
			{
				printf("INF ");
			}
			else
			{
				printf("%d ", a[start][goal]);
			}
		}
		printf("\n");
	}
	printf("\n\n");
}

int main()
{
	PrintGraph(a);

	floydWarshall();
	printf("after FloydWarshall \n");
	PrintGraph(a);
	
	return 0;
}

n번 만큼의 루프 연산이 삼겹으로 들어가므로 O(n³) 만큼의 시간복잡도를 가진다

실행결과

위에서 봤던 최종 결과 표와 일치한 결과를 볼 수 있다.

• 대량의 범위 안에서 소수들을 판별할때 사용
• 체를 쳐내듯이 합성수를 하나하나 지워나가며 소수만을 골라냄

/*
The Sieve of Erathosthenes 
에라토스테네스의 체

대량의 소수를 한꺼번에 판별할 수 있는 알고리즘

*/

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int number = 100000; //범위
int a[100001]; //수들을 넣을 배열

// 간단한 소수 판별 알고리즘
bool isPrimeNumber(int _x)
{
	int end = (int)sqrt(_x);

	for (int i = 2; i <= end; i++)
	{
		if (_x % i == 0)
		{
			return false;
		}
	}
	return true;
}

//에라토스테네스의 체
void primeNumberSieve()
{
	//초기화, 배열을 2부터 시작해서 정해진 범위까지 채워넣기
	for (int i = 2; i <= number; i++)
	{
		a[i] = i;
	}

	//합성수들을 지우기, 합성수 : 1과 자기자신 이외의 약수의 개수가 3개 이상인 자연수
	for (int i = 2; i <= number; i++)
	{
		if (a[i] == 0) //이미 지워진 수는 제외
		{
			continue;
		}
		
		for (int j = i + i; j <= number; j += i)
		{
			a[j] = 0; // 합성수들을 지우기
		}
	}

	for (int i = 2; i <= number; i++)
	{
		if (a[i] != 0) //지워진 수들을 제외하고 출력, 소수들을 출력
		{
			printf("%d ", a[i]);
		}
	}


}


int main()
{
	//printf("%d", isPrimeNumber(97));
	primeNumberSieve();
	return 0;
}

위의 코드에서 합성수들을 지우는 과정을 살펴보면

i와 j가 일정한 규칙으로 초기화가 되는데 아래와 같다

i == 2, j == 4
i == 2, j == 6
i == 2, j == 8
i == 2, j == 10
i == 2, j == 12
i == 2, j == 14
i == 2, j == 16
i == 2, j == 18

i == 3, j == 6
i == 3, j == 9
i == 3, j == 12
i == 3, j == 15
i == 3, j == 18
i == 3, j == 21
i == 3, j == 24
i == 3, j == 27
...

위처럼 2의 배수, 3의 배수 등등 어떤 소수의 배수들로 j가 초기화 되고, 그런 j들을 배열에서 지워준다

그렇게 배열에 소수만 남게 된다

참고자료 : https://blog.naver.com/ndb796/221233595886

Priority Queue(우선 순위 큐)

• ADT(추상 자료형)
• 데이터 입력 순서에 상관 없이 우선 순위 순으로 처리된다.
• 배열 기반 Heap 을 통해 구현
• scheduler, 네트워크 트래픽 제어 등에 쓰임

※ADT(Abstract Data Type)

어떤 자료형이 가지는 기능과 속성만 명시하고 자료형의 구체적인 구현 방법은 명시하지 않은것

Heap(Max Heap, Min Heap)

• 최대값또는 최소값을 빠르게 찾기 위해 쓰인다
• Complete Binary Tree(완전 이진 트리) 이다
• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.
• 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워야 한다.
• 배열로 구현한다
• Max Heap 은 항상 부모 노드의 값이 자식노드의 값보다 크다 그래서 root 노드의 값은 최대값이 온다. 최대 값을 빠르게 구할 수 있다.
• Min Heap 은 항상 부모 노드의 값이 자식노드의 값보다 작다, 최소값을 빠르게 구할 수 있다.
• 노드 개수를 알면, 트리구조는 무조건 확정할 수 있다.

Heapify algorithm

모든 노드의 위치가 heap 구조를 만족하도록, 위치를 조정하는 알고리즘

어떤 노드가 힙 구조(max-heap 이면 부모노드가 항상크다, min-heap 은 그 반대)를 위반하고 있을때, 그 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘, 위치를 바꾼 뒤에도 여전히 자식이 존재하는 경우, 또 자식 중에서 더 큰 자식과 자신의 위치를 바꾸어야 한다. 자식이 더 이상 존재하지 않을 때 까지 이과정은 계속 반복된다.(min-heap 은 반대로 부모 노드가 항상 자식들 보다 작게 위치를 조정한다)

시간 복잡도 :

한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다 O(nlogn)

그러나 실제로는 n/2 개수 만큼만 연산을 해줘도 Heapify가 완료 된다 그래서

실제 시간 복잡도는 O(n) 이다

힙 트리 와 배열 인덱스 관계

위 트리 노드의 숫자는 곧 완전 이진트리의 삽입 순서이자, 배열로 힙트리를 표현할때 각각 노드의 인덱스와 동일하다

i번 노드의 부모는 heap[(i / 2)]

i번 노드의 왼쪽 자식은 heap[(2*i)]

i번 노드의 오른쪽 자식은 heap[(2*i) + 1]

Insert(삽입)

1.삽입할 데이터를 가장 마지막 자리에 놓기

2.삽입한 데이터의 값을 부모노드와 비교해서 크면 부모노드와 위치를 바꾼다

이것을 부모노드가 더 클때까지 반복한다(heapify algorithm)

version 1

void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

version 2

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}

Pop(가장 첫번째 원소 삭제와 동시에 빼오기) 

Pop은 std::priority_queue 기준으로 삭제만 되게 되어있다. https://en.cppreference.com/w/cpp/container/priority_queue/pop

지금부터 구현하는 Pop함수는 약간 변형해서 반환까지 하게 한것이다.

힙트리 특성상 루트 노드의 값을 반환하게 되어있고, Max Heap 에서는 최대값, Min Heap 에서는 최소값을 꺼내게 되어있다.

1.루트 노드값(최대값, 최소값)을 꺼낸다

2.제일 마지막에 위치한 데이터를 루트로 옮긴다

3.자식 노드중에 가장 큰 값의 자리와 바꾼다

이것을 자식 노드보다 클때까지 반복한다(heapify algorithm)

version 1

int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

version 2

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}

전체 코드

#include <stdio.h>
#include <stdlib.h>

#define DEFAULT_HEAP_MAXSIZE 7

typedef struct _tagMaxHeap
{
	int* iDataArr;
	int iSize;
} Max_Heap;

void Swap_int(int* _a, int* _b);

void InitHeap(Max_Heap* _heap);
void Insert(Max_Heap* _heap, int _iData);
void Insert_2(int* arr2, int key, int input);
int Pop(Max_Heap* _heap);
int Pop_2(Max_Heap* _heap);

int main()
{
	Max_Heap heap;

	InitHeap(&heap);
	Insert(&heap, 8);
	Insert(&heap, 3);
	Insert(&heap, 15);
	Insert(&heap, 6);
	Insert(&heap, 10);
	Insert(&heap, 2);
	Insert(&heap, 18);
	
	/*	
	Insert_2(heap.iDataArr, ++heap.iSize, 8 );
	Insert_2(heap.iDataArr, ++heap.iSize, 3 );
	Insert_2(heap.iDataArr, ++heap.iSize, 15 );
	Insert_2(heap.iDataArr, ++heap.iSize, 6 );
	Insert_2(heap.iDataArr, ++heap.iSize, 18 );
	Insert_2(heap.iDataArr, ++heap.iSize, 2 );
	Insert_2(heap.iDataArr, ++heap.iSize, 10 );
	*/

	for (int i = 0; i < DEFAULT_HEAP_MAXSIZE; i++)
	{
		printf("%d ", Pop_2(&heap));
	}

	return 0;
}

void InitHeap(Max_Heap* _heap)
{
	_heap->iDataArr = (int*)calloc(DEFAULT_HEAP_MAXSIZE, sizeof(int));
	_heap->iSize = 0;
}


/*
i번 노드의 왼쪽 자식 == heap[(2*i)]
i번 노드의 오른쪽 자식 == heap[(2*i) + 1]
i번 노드의 부모 == heap[(i / 2)]
*/
void Insert(Max_Heap* _heap, int _iData)
{
	int* arr = _heap->iDataArr;
	int* iSize = &_heap->iSize;


	int currentIndex = ++(*iSize); //맨마지막 노드 인덱스 가져오기


	/*
	맨 마지막 노드에 데이터를 삽입, 해당 데이터가 부모 보다 크면 부모와 위치를 바꾸고 아니면 그대로 둠 
	*/
	while ((currentIndex != 1) && (_iData > arr[currentIndex / 2])) //root가 아니다 && 삽입 데이터가 현재노드의 부모보다 크다
	{
		arr[currentIndex] = arr[currentIndex / 2]; // 자식 노드자리에 부모 노드 값을 대입, 부모노드가 작으므로 밑으로 내림
		currentIndex /= 2; // 현재 인덱스에 부모 인덱스 대입
	}
	arr[currentIndex] = _iData; //최종 위치에 삽입
}

void Insert_2(int* arr2, int key, int input)
{
	arr2[key] = input; // 마지막 노드에 입력값 넣기

	while (key > 1)  //root에 도달할때까지 반복
	{
		if (arr2[key] > arr2[key / 2])  // 부모 노드보다 더 크다면
		{
			Swap_int(&arr2[key], &arr2[key / 2]); // 부모 노드와 자리를 바꿈
			key /= 2; // 부모노드 인덱스로 전환
		}
		else
		{
			break;
		}
	}
}



int Pop(Max_Heap* _heap)
{
	if (_heap->iSize == 0)
	{
		return 0;
	}

	int ret = _heap->iDataArr[1]; // 꺼내올 데이터(root)
	_heap->iDataArr[1] = _heap->iDataArr[_heap->iSize--]; // root 자리에 맨마지막 위치 데이터 대입
	int parent = 1; //root 부터 시작
	int child = 0;
	
	while (1)
	{
		child = parent * 2; //왼쪽 자식, i번 노드의 왼쪽 자식 == heap[(2*i)]
		if (child + 1 <= _heap->iSize && _heap->iDataArr[child] <= _heap->iDataArr[child + 1]) // 오른쪽 자식 인덱스가 존재한다 && 오른쪽 자식이 왼쪽 자식보다 크거나 같다
		{
			child++; //오른쪽 자식으로 전환
		}

		if (child > _heap->iSize || _heap->iDataArr[child] < _heap->iDataArr[parent]) //자식인덱스가 힙 사이즈보다 크다(범위를 넘어버림) || 부모가 제일 큰 자식 보다 크다 
		{
			break; //중단
		}

		Swap_int(&_heap->iDataArr[parent], &_heap->iDataArr[child]); //부모와 제일 큰 자식 자리를 바꿈
		parent = child; // 자식의 자식들을 비교하기위해, 자식 노드를 부모 노드로 봄
	}
	return ret; // 꺼내올 데이터 리턴
}

int Pop_2(Max_Heap* _heap)
{
	int result = _heap->iDataArr[1]; //꺼내올 데이터
	
	int* arr = _heap->iDataArr; 
	int* iSize = &_heap->iSize;
	
	Swap_int(&arr[1], &arr[*iSize]); //마지막 노드 데이터와 루트 데이터를 바꿈
	(*iSize)--; //전체 노드 갯수 감소

	int parentIdx = 1; 
	int childIdx = parentIdx * 2;

	if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
	{
		childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
	}

	while (childIdx <= *iSize && arr[parentIdx] < arr[childIdx]) //자식 인덱스가 범위를 넘지 않는다 && 자식노드가 부모노드 보다 크다
	{
		Swap_int(&arr[parentIdx], &arr[childIdx]); // 자식 노드와 부모노드 위치 바꾸기

		parentIdx = childIdx; //자식 노드를 부모 노드로 봄
		childIdx *= 2; //왼쪽 자식 노드

		if (childIdx + 1 <= *iSize) //오른쪽 자식 노드 인덱스가 노드 전체 갯수를 넘지 않는다, 즉 오른쪽 자식이 존재한다
		{
			childIdx = (arr[childIdx] > arr[childIdx + 1]) ? childIdx : childIdx + 1; //왼쪽 자식, 오른쪽 자식, 둘 중에 큰 노드 선별
		}
	}
	return result;
}


void Swap_int(int* _a, int* _b)
{
	*_a ^= *_b ^= *_a ^= *_b;
}

실행결과

삽입한 순서에 상관없이 우선 순위(노드 값이 높을 수록 우선순위가 높다고 할때) 순으로 

데이터를 꺼내오고 있다.

Tree

• 계층적 구조를 나타내는 자료구조

• 부모-자식 관계의 노드들로 구성, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태

• 자식 -> 부모, 등으로 순환 할 수 없음, 무조건 부모 -> 자식 방향으로만 뻗어나감

• Linked List의 장점 을 가지고 있음( 데이터 삽입, 삭제시 데이터들을 이동하지 않아도 되는것)

• Linked List의 단점을 보완함(검색시 노드의 처음부터 찾아가야 하는 것, 이진 탐색)

• 노드가 3개 붙으면 ternary tree, 2개 붙으면 binary tree 라고 함, 주로 binary tree를 가장 많이 씀

Tree 용어 정리

• 부모(parent) 노드 : 어떤 노드 바로 위에 연결되어있는 노드

• 자식(child) 노드 : 어떤 노드 바로 아래에 연결되어 있는 노드

• 형제(sibling) 노드 : 같은 부모를 가지는 노드

• 조상(ancestor) : 어떤 노드에서 root 노드에 이르는 경로상에 있는 노드들

• 자손(descendent) : 어떤 노드의 자식 노드를 포함하여, 아래쪽에 있는 노드들

• 루트(root) : 부모가 없는 노드

• 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리

• 잎(leaf) 노드 : 자식 노드가 하나도 없는 노드, 외부(external) 노드라고도 불림

• 내부(internal) 노드 : 잎노드가 아닌 노드, 자식 노드를 하나라도 가지고 있는 노드

• 수준(level) : 트리의 각 계층에 매겨지는 번호, root 노드의 level 은 1, 한층씩 내려갈 수록 1씩 증가

• 높이(height) : 트리에 속한 노드의 최대 수준, 위 트리의 높이는 4

가중치는 서울 교통 공사 사이버 스테이션(http://www.seoulmetro.co.kr/kr/cyberStation.do) 에서

나오는 거리(km)를 기반으로 하였음

/*
다익스트라 알고리즘

*/

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define INF 1000 //무한, 인접해있지 않은 경우 무한으로 처리, 
//여기서는 가중치를 다 더해서 나올수 없는 큰수 1000으로 하였음

//지하철 노선도
#define VERTEX_COUNT 13
int adj[VERTEX_COUNT][VERTEX_COUNT] =
{
	{INF, 9, INF, 8, INF, INF, 6, 10, INF, INF, INF, INF, INF},      // 0. 종로3가 : 종로5가, 종각, 을지로3가, 을지로4가
	{9, INF, 8, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},   // 1. 종로5가 : 종로3가, 동대문
	{INF, 8, INF, INF, INF, INF, INF, INF, 7, INF, INF, INF, INF},   // 2. 동대문 : 종로5가, 동대문역사문화공원
	{8, INF, INF, INF, 10, INF, INF, INF, INF, INF, INF, INF, INF},  // 3. 종각 : 종로3가, 시청
	{INF, INF, INF, 10, INF, 7, INF,  INF, INF, 11, INF, INF, INF},  // 4. 시청 : 종각, 을지로 입구, 서울역 
	{INF, INF, INF, INF, 7, INF, 8,  INF, INF, INF, INF, INF, INF},  // 5. 을지로입구 : 시청, 을지로3가
	{6, INF, INF, INF, INF, 8, INF,  6, INF, INF, INF, INF, 7},      // 6. 을지로3가 : 종로3가, 을지로입구, 을지로4가, 충무로
	{10, INF, INF, INF, INF, INF, 6, INF, 10, INF, INF, INF, INF},   // 7. 을지로4가 : 종로3가, 을지로3가, 동대문역사문화공원
	{INF, INF, 7, INF, INF, INF, INF, 10, INF, INF, INF, INF, 13},   // 8. 동대문역사문화공원 : 동대문, 을지로4가, 충무로
	{INF, INF, INF, INF, 11, INF, INF,  INF, INF, INF, 9, INF, INF}, // 9. 서울역 : 시청, 회현
	{INF, INF, INF, INF, INF, INF, INF, INF, INF, 9, INF, 7, INF},   // 10. 회현 : 서울역, 명동
	{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 7, INF, 7},   // 11. 명동 : 회현, 충무로
	{INF, INF, INF, INF, INF, INF, 7, INF, 13, INF, INF, 7, INF}     // 12. 충무로 : 을지로3가, 동대문역사문화공원, 명동
};

enum eStation
{
	종로3가,
	종로5가,
	동대문,
	종각,
	시청,
	을지로입구,
	을지로3가,
	을지로4가,
	동대문역사문화공원,
	서울역,
	회현,
	명동,
	충무로
};

char* vertexToStationName(int _vertexIndex); //정점 인덱스 -> 문자열 정점이름

//경로 확인 하기 위한 구조체, 간선의 시작점과 끝점을 의미
typedef struct _tagRoutePair
{
	int ParentV; //시작점
	int ChildV; //끝점
} ROUTEPAIR;

void Dijkstra(int _startV, int _endV)
{
	bool visited[VERTEX_COUNT] = { 0 }; //방문기록
	int distance[VERTEX_COUNT]; //시작점에서 각정점까지의 최소 가중치(최단거리) 기록
	ROUTEPAIR routePairs[VERTEX_COUNT] = { 0 }; //경로확인을 위한 간선 저장 배열
	
	//최소가중치 기록 배열 초기화
	for (int i = 0; i < VERTEX_COUNT; i++)
	{
		distance[i] = INF;
	}
	//distance[_startV] = 0;

	//주변 정점들과의 최소 가중치 기록하기
	for (int i = 0; i < VERTEX_COUNT; i++)
	{
		if (adj[_startV][i] != INF)
		{
			distance[i] = adj[_startV][i];
		}
	}
	visited[_startV] = true;
	routePairs[_startV].ParentV = _startV;

	int curretV = _startV; 
	for(int i = 0; i < VERTEX_COUNT - 1; i++)
	{
		int min = INF;
		int minIdx = curretV;

		for (int i = 0; i < VERTEX_COUNT; i++) //방문하지 않고, 최소 가중치 기록중 제일 낮은 가중치를 가지는 정점 찾기
		{
			if (!visited[i]) 
			{
				if (min > distance[i])
				{
					min = distance[i];
					minIdx = i; 
				}
			}
		}
		
		//기준 정점 초기화 및 방문 처리
		curretV = minIdx; 
		visited[curretV] = true;

		//방문한 정점을 기준으로 최소 가중치 배열 수정
		for (int i = 0; i < VERTEX_COUNT; i++)
		{
			if (!visited[i])
			{
				if (distance[curretV] + adj[curretV][i] < distance[i]) //이전경로 가중치 + 인접경로(새경로) 가중치
				{
					//경로 저장
					routePairs[curretV].ChildV = i;
					routePairs[i].ParentV = curretV;
				
					distance[i] = distance[curretV] + adj[curretV][i]; // 더 빠른 경우 초기화
				}
			}
		}
	
	}

	//반드시 adj 0번째 배열을 _start로 해야 아래로직이 무한루프 돌지 않고 잘동작함
	//_start 가 adj[0] 이 아닐 경우, 무한루프

	//경로 확인 하기
	int routeStack[VERTEX_COUNT] = { 0 };
	int RoutesCount = 0;
	routeStack[RoutesCount++] = _endV;
	int now = _endV;
	while(1)
	{
		if (routePairs[now].ParentV == _startV)
		{
			routeStack[RoutesCount++] = _startV;
			break;
		}
		now = routePairs[now].ParentV;
		routeStack[RoutesCount++] = now;
	}

	for (int i = RoutesCount - 1; i >= 0; i--)
	{
		
		if (i == RoutesCount - 1)
		{
			printf("%s 시작\n", vertexToStationName(routeStack[i]));
		}
		else if (i == 0)
		{
			printf("%s 도착\n", vertexToStationName(routeStack[i]));
		}
		else
		{
			printf("%s 방문\n", vertexToStationName(routeStack[i]));
		}
	}

}

char* vertexToStationName(int _vertexIndex)
{
	enum eStation e = _vertexIndex;
	switch (e)
	{
	case 종로3가:
		return "종로3가";
	case 종로5가:
		return "종로5가";
	case 동대문:
		return "동대문";
	case 종각:
		return "종각";
	case 시청:
		return "시청";
	case 을지로입구:
		return "을지로입구";
	case 을지로3가:
		return "을지로3가";
	case 을지로4가:
		return "을지로4가";
	case 동대문역사문화공원:
		return "동대문역사문화공원";
	case 서울역:
		return "서울역";
	case 회현:
		return "회현";
	case 명동:
		return "명동";
	case 충무로:
		return "충무로";
	default:
		return "없음";
	}
}


int main()
{
	Dijkstra(종로3가, 회현);
	
	return 0;
}

다익스트라(Dijkstra) 알고리즘

• 에츠허르 비버 데이크스트라(Edsger Wybe Dijkstra)가 1956년에 고안했으며 1959년에 발표

• 하나의 시작 정점에서 모든 다른 정점까지 최소비용의 인접정점을 선택하여 최단경로를 찾는 알고리즘

• 입력 그래프에서 간선들의 가중치가 모두 0 이상인경우에 쓰임, 음수 가중치는 지원되지 않음(벨만-포드 알고리즘은 음수 가중치 허용)

• 최단 경로는, 경로의 길이 순으로 정해짐

• 다이나믹 프로그래밍 문제(큰문제를 작은 문제로 나누어 푸는 문제)로 분류, 최단거리는 여러 개의 최단거리로 이루어져있기 때문이다

• 가중치를 계산해서 효율적인 것 부터 방문하는 알고리즘

• 인공위성 GPS 소프트웨어 등에서 가장 많이 사용됨
  
  
  

다익스트라 알고리즘 순서

  1. 시작점을 기준으로 아직 방문하지 않았고 인접한 정점들까지의 최소 가중치 정리

  2. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

  3. 선별한 정점 방문, 방문한 정점 주변에 방문하지 않고 인접한 정점들을 파악

  4. 방문하지 않고 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

5. (전체 정점 개수 - 1(시작점)) 회 만큼 2~4 과정 반복

다익스트라 알고리즘 동작 과정 파헤치기

1. 시작 정점을 기준으로 모든 정점에 이르는 최소 가중치(최단거리)를 구해본다 이때 인접한 정점들은 가중치 계산이 되지만, 인접하지 않은 정점들은 어떤 점들을 경유해서 가야 될텐데, 아직 어떤점들을 지나갈지 모르므로 가중치가 무한(0이 아닌 모든 가중치들의 합보다 큰 일정한 하나의 수)이라고 한다.

A_A는 A에서 A까지 도달하는 거리므로 사실상 0과 다름없다.

2. 인접한 정점들중 제일 낮은 가중치를 가진 정점(해당 예시에서는 G = 6)을 방문처리 한다.

3. 방문한 정점을 기준으로 다시 인접하며, 아직 방문하지 않은 정점들을 찾는다,

이때 아까 인접하지 않았서 가중치를 무한으로 했던 정점들도 발견할 수 있는데, 지금 기준 정점(지금까지 제일 낮은 가중치)을 경유하여 오게 되므로, 지금 기준 정점까지의 최소 가중치 + 해당 정점들 까지의 가중치 와 현재 기록되있는 최소가중치와 비교하여 더 빠르면 기입하고, 빠르지 않으면 그대로 둔다.

A_F = INF > A_G(6) + G_F(8) ? A_G(6) + G_F(8) : A_F(INF); //바뀜

A_H = 10 > A_G(6) + G_H(6) ? A_G(6) + G_H(6)  : A_H(10); //바뀜

A_M = INF > A_G(6) + G_M(7) ? A_G(6) + G_M(7) : A_M(INF); //바뀜

4. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

위표를 기준으로 D가 제일 작고, 방문하지 않았으므로 D가 선택됐다.

5. 선별한 정점(D) 방문, 방문한 정점 주변에 인접한 정점들을 파악

6. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_E = A_E(INF) > A_D(8) + D_E(10) ? A_D(8) + D_E(10) : A_E(INF); //바뀜

7.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

B가 선택됐다.

8. 선별한 정점(B) 방문, 방문한 정점 주변에 인접한 정점들을 파악

9. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_C = A_C(INF) > A_B(9) + B_C(8) ? A_B(9) + B_C(8) : A_C(INF); //바뀜

10. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

H가 선택됐다

11. 선별한 정점(H) 방문, 방문한 정점 주변에 인접한 정점들을 파악

12. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_I = A_I(INF) > A_H(10) + H_I(10) ? A_H(10) + H_I(10) : A_I(INF); // 바뀜

13. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

M이 선택됐다

14. 선별한 정점(M) 방문, 방문한 정점 주변에 인접한 정점들을 파악

15. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_I = A_I(20) > A_M(13) + M_I(13) ? A_M(13) + M_I(13) : A_I(20) // 그대로

A_L = A_L(INF) > A_M(13) + M_L(7) ? : A_M(13) + M_L(7) : A_L(INF) // 바뀜

16. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

F 가 선택됐다

17. 선별한 정점(F) 방문, 방문한 정점 주변에 인접한 정점들을 파악

18. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_E = A_E(18) > A_F(14) + F_E(7) ? A_F(14) +F_E(7) : A_E(18) // 그대로

19. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

C가 선택됐다.

20. 선별한 정점(C) 방문, 방문한 정점 주변에 인접한 정점들을 파악

21. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_I = A_I(20) > A_C(17) + C_I(7) ? A_C(17) + C_I(7) : A_I(20) // 그대로

22. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

E로 선택됐다.

23. 선별한 정점(E) 방문, 방문한 정점 주변에 인접한 정점들을 파악

24. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_J = A_J(INF) > A_E(18) + E_J(11) ? A_E(18) + E_J(11)  : A_J(INF) // 바뀜

25.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

※I 와 L 둘다 안방문 했으면서, 그중에서 제일 작은 가중치 20을 동일하게 나타내고 있다, 이럴때는 for문과 배열을 사용한다는 것을 감안하여 순차적으로 I부터 방문한다

26.선별한 정점(I) 방문, 방문한 정점 주변에 인접한 정점들을 파악

27.인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

※인접하면서 아직 방문하지 않은 정점이 주변에 하나도 없으므로 과정이 생략된다(반복문 안에 조건문을 만족시키지 못하고 계속 continue 되어 결국 반복문이 끝나고 다음 순서, 최소 가중치 정점 선별로 넘어가 버린다.)

28.최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

L 이 선택됐다.

29. 선별한 정점(L) 방문, 방문한 정점 주변에 인접한 정점들을 파악

30. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_K = A_K(INF) > A_L(20) + L_K(7) ? A_L(20) + L_K(7)  : A_K(INF) // 바뀜

31. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

K가 선택됐다.

32. 선별한 정점(K) 방문, 방문한 정점 주변에 인접한 정점들을 파악

33. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

(현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

A_J = A_J(29) > A_K(27) + K_J(9) ? A_K(27) + K_J(9)  : A_J(29) // 그대로

34. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별

J가 선택됐다.

35. 선별한 정점(J) 방문, 방문한 정점 주변에 인접한 정점들을 파악

36. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠

※인접하면서 아직 방문하지 않은 정점이 주변에 하나도 없으므로 과정이 생략된다(반복문 안에 조건문을 만족시키지 못하고 계속 continue 되어 결국 반복문이 끝나고 다음 순서, 최소 가중치 정점 선별로 넘어가 버린다.)

37. 해당 그래프를 기준으로 여기까지 하면 총 11회 방문, 즉 정확히 전체정점 개수(12) - 1 만큼,  아래 과정을 반복하게 된다.

1. 최소 가중치들 중에 아직 방문하지 않으면서 제일 작은 가중치를 가진 정점 선별
2. 선별한 정점 방문, 방문한 정점 주변에 인접한 정점들을 파악
3. 인접한 정점들중 시작점을 기준으로 해당 정점들까지의 최소 가중치 구해서 비교한뒤 빠르면 정리해놓은 최소 가중치를 수정, 느리면 그대로둠
   • (현재 기준점 까지의 최소가중치)+(인접한 정점까지의 가중치) < 현재 기록되어있는 최소 가중치

알고리즘이 종료 되면, 지금까지 초기화 시켰던 최소 가중치 정리 배열에는 시작점(A)로 부터 각각 정점까지 가는데 드는 최소 비용을 정리해 놓게 된다.

예를들면 A(시작점) 에서 정점 K 까지 간다고 했을때, A -> D -> E  -> J -> K로 거쳐서 갈 수도 있겠지만

가중치 크기 비교를 하면

A -> G -> M -> L -> K( A_G + G_M + M_L + L_K )가  A -> D -> E  -> J -> K(A_D + D_E + E_J + J_K) 보다 작다,

즉 더 빠르게 갈 수 있다는 뜻이고, 이렇게 다양한 정점들 속에서 나올 수 있는 최소비용, 즉 최단거리들을 기록해 놓은 것이 위의 표이고, 곧 지금까지의 과정 Dijkstra 알고리즘을 통해서 구할 수 있는 것이다.

깊이 우선 탐색(Depth First Search) _ 재귀호출

• 맹목적으로 각 vertex를 탐색할 때 주로 사용

• 더이상 나아가지 못할때 까지 깊이 탐색하면서 나아감

• Binary Search Tree의 재귀호출로 순회하는 함수(InOrder, PreOrder, PostOrder)들이 대표적인 예가 될 수 있다

• 스택(Stack) 또는 재귀 호출이 사용된다.

재귀 호출 DFS 알고리즘 순서

1.시작점으로 vertex를 인자로 DFS 함수 호출

2.해당 vertex를 방문했다는 사실을 기록

3.해당 vertex와 인접하고 방문하지 않은 vertex를 인자로 DFS 함수를 호출

2~3 과정이 모든 vertex들을 방문할때까지 되풀이 된다.

위 그래프의 인접행렬을 이차원배열로 표현한뒤, DFS또한 구현하여 실행해봤다.

코드

constexpr int VERTEX_COUNT = 8;
constexpr int adj[VERTEX_COUNT][VERTEX_COUNT] =
{
	{0, 1, 1, 0, 0, 0, 0, 0}, //v0  : v1, v2
	{1, 0, 0, 1, 1, 0, 0, 0}, //v1  : v0, v3, v4
	{1, 0, 0, 0, 0, 1, 1, 0}, //v2  : v0, v5, v6
 	{0, 1, 0, 0, 0, 0, 0, 1}, //v3  : v1, v7
	{0, 1, 0, 0, 0, 0, 0, 1}, //v4  : v1, v7
	{0, 0, 1, 0, 0, 0, 0, 1}, //v5  : v2, v7
	{0, 0, 1, 0, 0, 0, 0, 1}, //v6  : v2, v7
	{0, 0, 0, 1, 1, 1, 1, 0}  //v7  : v3, v4, v5, v6
};

bool visited[VERTEX_COUNT]; //방문기록

void DFS_Recursive(int _start)
{
	visited[_start] = true; //방문
	printf("%d 방문\n", _start);
	for (int i = 0; i < VERTEX_COUNT; i++)
	{
		if (adj[_start][i] == 1 && !visited[i])//인접했다 && 방문안했다 
		{
			DFS_Recursive(i); //재귀호출, 인접한 vertex를 인자로 대입
		}
	}
}

int main()
{
	DFS_Recursive(0); 
	return 0;
}

실행결과

실행결과를 보면 화살표 번호 순서대로 방문하는 것을 알 수 있다.

이과정을 자세히 들여다보면 처음 시작은 0부터 시작하므로 0을 인자로 넣어서 V0을 방문 V0에서 인접하며, 방문하지 않은 V1발견, V1을 인자로 재귀호출을 시작하게 된다. 아래 순서 번호는 곧 위 그림의 화살표 번호과 같다.

1. V1을 방문, V1에서 인접하며, 방문하지 않은 V3발견, V3을 인자로 재귀호출                                        현재 누적 방문 : V0, V1                                                                                                             

2. V3을 방문, V3에서 인접하며, 방문하지 않은 V7발견, V7을 인자로 재귀호출                                                        현재 누적 방문 : V0, V1, V3                                                                                                                         

3. V7을 방문, V7에서 인접하며, 방문하지 않은 V4발견, V4을 인자로 재귀호출                                    현재 누적 방문 : V0, V1, V3, V7                                                                                                  
4. V4을 방문, V4에서 인접하며, 방문하지 않은 vertex가 없으므로 재귀호출 하지 않고 함수가 끝남          현재 누적 방문 : V0, V1, V3, V7, V4                                                                                           
5. V7을 인자로 가졌던 함수로 돌아감(rewind), V7에서 인접하며 방문하지 않은 V5발견, V5을 인자로 재귀호출                                                                                                                           현재 누적 방문 : V0, V1, V3, V7, V4                                                                                                                                                                                                                                                                                                                                                                     
6. V5을 방문, V5에서 인접하며, 방문하지 않은 V2발견, V2을 인자로 재귀호출                                     현재 누적 방문 : V0, V1, V3, V7, V4, V5                                                                                         
7. V2을 방문, V2에서 인접하며, 방문하지 않은 V6발견, V6을 인자로 재귀호출                                    현재 누적 방문 : V0, V1, V3, V7, V4, V5, V2                                                                              
8. V6을 방문, V6에서 인접하며, 방문하지 않은 vertex가 없으므로 재귀호출 하지 않고 함수가 끝남 이때부터는 모두 방문했으므로 rewind 되는 것만 남음                                                                  현재 누적 방문 : (모두 방문 완료)V0, V1, V3, V7, V4, V5, V2, V6                                                                                                                                                                                      
9. V2을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
10. V5을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
11. V7을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
12. V3을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
13. V1을 인자로 가졌던 함수로 돌아감, 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남
14. V0을 인자로 가졌던 함수로 돌아감(처음 호출했던 함수), 모두 방문했으므로, 재귀호출 하지 않고 함수가 끝남

너비 우선 탐색(Breadth First Search)

• Vertex 들을 각각 다 한번씩 방문하는데, 넓고 얕게 탐색해 나간다
• Queue 가 사용된다.
• 최단 거리 찾기에 사용할 수 있지만, 간선들의 가중치가 모두 동일할 때만 쓰인다(미로)

알고리즘 순서

1. Queue에 맨처음 시작 vertex를 넣기
2. 시작 vertex를 방문 처리 해주기
3. Queue 에서 pop(가장 먼저 들어간 vertex) 꺼내기
4. 꺼낸 vertex 에 연결된 vertex 중 방문하지 않은 vertex 들을 방문 처리하고 차례대로 방문 처리한 vertex 들을 queue에 삽입
5. 모두 방문할때 까지 3번, 4번 과정 반복

위 그래프의 인접행렬을 이차원배열로 표현한뒤, BFS또한 구현하여 실행해봤다.

코드

/*
이차원 배열로 그래프의 인접행렬을 표현
배열의 세로축은 정점(vertex)
각각 정점에 대한 가로축 인덱스는 곧 정점 인덱스이며
실제로 들어가는 값은 0 또는 1 이 들어가며  
인접관계에 있어서 true or false를 뜻한다
ex) adj[1][2] //V1 정점과 V2정점과의 인접관계
*/

constexpr int VERTEX_COUNT = 8;
constexpr int adj[VERTEX_COUNT][VERTEX_COUNT] =
{
	{0, 1, 1, 1, 0, 0, 0, 0}, //v0  : v1, v2, v3
	{1, 0, 0, 0, 1, 0, 0, 0}, //v1  : v0, v4
	{1, 0, 0, 0, 0, 1, 1, 0}, //v2  : v0, v5, v6
 	{1, 0, 0, 0, 0, 0, 0, 1}, //v3  : v0, v7
	{0, 1, 0, 0, 0, 0, 0, 0}, //v4  : v1
	{0, 0, 1, 0, 0, 0, 0, 0}, //v5  : v2
	{0, 0, 1, 0, 0, 0, 0, 0}, //v6  : v2
	{0, 0, 0, 1, 0, 0, 0, 0}  //v7  : v3
};

//방문기록을 저장할 배열, 방문하면 true 처리
bool visited[VERTEX_COUNT]; 

void BFS(int _start)
{
	std::queue<int> q; //queue 선언
	q.push(_start); //맨처음 시작 vertex 를 넣기
    visited[_start] = true; //시작 vertex 방문 처리 해주기
	printf("시작 %d 방문\n", _start);
	
    
    //모든 vertex를 방문해서 더이상 queue에 넣을 vertex가 없어서
    //queue가 비어있을 때까지 반복
    while (!q.empty()) 
	{
        //queue에서 가장먼저 넣은 vertex 꺼내기
		int y = q.front(); //queue 에서 front(가장 먼저 넣은 vertex) 값 복사
		q.pop(); //복사 했으니 제거
        
        
		for (int x = 0; x < VERTEX_COUNT; x++)  
		{
			if (adj[y][x] == 0) //인접하지 않으면 skip
			{
				continue;
			}
			else //인접하다면
			{
				//방금꺼낸 vertex 와 인접한 vertex들을 하나씩 가져오기
				if (!visited[x]) //방문했는지 체크, 안했다면
				{
					q.push(x); //queue에 삽입
					visited[x] = true; //방문처리
					printf("%d 방문\n", x);
				}
			}
		}
	}
}

int main()
{
	BFS(0);
	return 0;
}

실행결과

위 콘솔창 실행결과와 오른쪽 그래프를 보면, 화살표 순서대로 실행해 나갔다는것을 알 수 있으며

Breadth First Search(너비 우선 탐색) 알고리즘은 넓고 얕게 탐색해 나간다는 것을 알 수 있다.

Graph(그래프) 기본 용어 정리 및 표현

Graph(그래프)란?

• 현실세계의 사물이나 추상적인 개념간의 연결관계를 정점(vertex)과 간선(edge)으로 표현한것

정점(vertex) : 데이터를 표현 (사물, 개념)

간선(edge) : 정점들을 연결 하는데 사용

G = (V, E) 

V = {A, B, C, D, E}      //정점들의 집합

E = {e1, e2, e3, e4, e5} //간선들의 집합

e1 = (A, B) //부속해 있는 정점들

e2 = (A, C)

e3 = (B, C)

e4 = (B, D)

e5 = (D, E)

코드로 표현하기

간선들의 가중치가 모두 동일하다는 전제하에 아래처럼 2차원 배열로 표현할 수 있다.

2차원 배열의 세로, 가로 모두 Vertex 들을 가리킨다

가로의 인덱스는 곧 vertex들의 순서이고

순서대로 A, B, C, D, E를 가리킨다

이때 0 또는 1로 표현하는데, 인접(adjacent)해 있다면 1로 표현하고

그렇지 않으면 0으로 표현한다

위와 같이 인접관계를 행렬(2차원 배열)로 표현한 것을 "인접 행렬" 이라고 한다

그외에도 2차원 배열이 아닌 리스트를 통해 인접관계를 표현한 것을 "인접 리스트" 이라고 한다 

그래서

vertex A는 인접해 있는 vertex가 B와 C 이므로

B index = 1

C index = 2

이기 때문에 1번째, 2번째 값에 1(true)이 들어간다

{0, 1, 1, 0, 0}, //A

vertex B는 A,C,D 이다

A index = 0

C index = 2

D index = 3

배열의 0번째, 2번째, 3번째에 1(true)이 들어간다

{1, 0, 1, 1, 0}, //B

이런식으로 정리하다 보면, 아래와 같이 정리가 된다.

{
    {0, 1, 1, 0, 0}, //A
    {1, 0, 1, 1, 0}, //B
    {1, 1, 0, 0, 0}, //C
    {0, 1, 0, 0, 1}, //D
    {0, 0, 0, 1, 0} //E
};

용어 정리

sparse graph : 노드의 수보다 엣지 수가 적은 그래프, vertex > edge

dense graph : 노드의 수 보다 엣지 수가 큰 그래프, vertex < edge

인접(incident), 부속(adjacent) : 위 그래프에서 vertex A와 C는 edge e2로 연결되어 있다, 이때 vertex A와 C는 서로 인접(adjacent)해 있다. 그리고 edge e2는 두 vertex A 와 C에 부속(incident)해 있다고 한다

degree : 하나의 vertex 에 연결된 edge 의 수

loop : 하나의 edge가 하나의 노드에만 부속해 있을때

isolated vertex : 하나의 vertex에 부속해 있는 edge가 전혀 없을때

adjacency matrix(인접 행렬) : 그래프 이론에서 인접 관계를 행렬로 표현한 것

adjacency list(인접 리스트) : 그래프 이론에서 인접 관계를 리스트로 표현한 것