코딩무식자 전공생

저번에 작성한 다익스트라의 구현1은 선형탐색으로 O(N^2)의 시간복잡도를 가지므로, 최단거리 알고리즘 문제를 풀 때 비효율적일 수 있습니다.

제가 갖고있는 2권의 자료구조책과 한권의 알고리즘책에도 구현의 난이도 때문인지 O(N^2)의 방법만 설명해주고있고, 구글링해본결과  우선순위 큐(힙)를 이용하여 O(NlogN)의 시간복잡도를 가지는 다익스트라의 구현법을 알게되어 직접 구현해보았습니다.정확하게 설명하자면 O(ElogV)입니다.

원리는 선형탐색의 방법과 똑같지만 내부구현방식만 다르고, 우선순위 큐의 구현을 글로 설명하는게 힘들어서 직접 그려보고 이해할 수 있게 저번과 같은 간단한 경우로 구현하였고, 헷갈릴 수 있는 부분은 최대한주석으로 작성해보았습니다.

주의 할 것은 우선순위큐에 삽입 시 거리를 음수화하여 삽입하고 뺄 때도 그 값을 음수화하여(결국 양수) 연산하는것입니다. 직접 그려보면 이해가 쉽습니다.

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int INF = 100000000;
vector<pair<int, int>>a[4];
int d[4];
void dijkstra(int start);
int main()
{
	for (int i = 0; i < 4; i++)
		//최초의 최단거리배열은 무한대로잡아두고시작
		d[i] = INF;
	
	a[0].push_back(make_pair(1, 5));
	a[0].push_back(make_pair(2, 1));

	a[1].push_back(make_pair(0, 5));
	a[1].push_back(make_pair(2, 2));

	a[2].push_back(make_pair(0, 1));
	a[2].push_back(make_pair(1, 2));
	a[2].push_back(make_pair(3, 3));

	a[3].push_back(make_pair(2, 3));
	dijkstra(0);
	for (int i = 0; i < 4; i++)
		cout << d[i] << " ";
	cout << endl;
}
void dijkstra(int start)
{
	//첫 노드와 첫 노드는 최단거리없으므로 0
	d[start] = 0;
	priority_queue<pair<int, int>>pq;
	//우선순위큐의 first는 거리, second는 노드(정점)의미
	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
	
		//설명을 돕기위해 0번(a)노드와 1번(b)노드,2번노드(c)를 예로들겠음
		//어짜피 첫 노드는 distacne=0,current=0이므로
		//0번노드를제외한 최초의 첫 번째 큐삽입연산은68행임 
		//67행에서 a와 맞닿아있는 b와의거리(5)와 c와의거리(1)이 삽입됨
		//이 때, 어떠한 음수의 조건이없다면, (5,1),(1,2)순으로 큐에저장됨
		//최단거리부터 알고 싶으므로 67행을 음수화하여 삽입하면 (-1,2),(-5,1)로 정렬됨
		//그렇기 때문에 47행에서 다시 뽑을 때 음수화하여 뽑으면 최단거리순으로 뽑게됨.
		int distance = -pq.top().first;
		int current = pq.top().second;
		pq.pop();

		//아래처럼 건너뛰는 연산식을 적어야 불필요한 연산을 줄일 수 있음
		//ex)(5,1)가 큐에있는데 3으로 이미 수정되어있으므로 볼필요도없으므로 
		//최단거리가 아니면 스킵한다.
		if (d[current] < distance)
			continue;

		for (int i = 0; i < a[current].size(); i++)
		{
			int next = a[current][i].first;
			//next_distance=0번~현재노드까지의 최단거리(계속 수정됨)+현재노드~탐색할노드의 거리
			int next_distance = distance + a[current][i].second;
			//기존의 최단거리보다 더 작은 값이면 그값으로 갱신
			if (d[next] > next_distance)
			{
				d[next] = next_distance;
				//음수화 삽입
				pq.push(make_pair(-next_distance, next));

			}
		}
	}
}

결과

선형탐색으로 구현한 일반적인 다익스트라 구현방법입니다.

직관적이고, 작성이쉬운 장점이 있으나, 최단거리를구하기위해 짧은거리부터 찾아나가는 연산과 전체적인 다익스트라를 수행하는 연산이 약 n^2번 까지도 돌 수 있으므로 평균 시간복잡도가 O(N^2)입니다.

아래 경우를 예시로 하여 0번노드에서부터의 다익스트라를 구현해보았습니다.

코드

#include<cstdio>
#define INF 21474836

#define MAX_VERTEX 4

int weight[MAX_VERTEX][MAX_VERTEX] =
{
	{0,5,1,INF},
	{5,0,2,INF},
	{1,2,0,3},
	{INF,INF,3,0}
};
bool visited[4];
int d[4];
void dijkstra(int start);
int  small_index();
int main()
{
	dijkstra(0);
	for (int i = 0; i < 4; i++)
		printf("%d ", d[i]);
	puts("");
}
void dijkstra(int start)
{
	for (int i = 0; i < 4; i++)
		d[i] = weight[start][i];
	visited[start] = 1;

	//첫째노드와 마지막 노드에서 최단거리를 구할필요는없으므로
	//i<4가 아닌 i<2
	for (int i = 0; i < 2; i++)
	{
		int current = small_index();
		visited[current] = 1;
		for (int j = 0; j < 4; j++)
		{
			if (!visited[j]) {
				//current까지의최단거리+현재~도착까지의거리<도착까지의최단거리라면,
				if ((d[current] + weight[current][j]) < d[j])
				{
					//작은값으로 갱신
					d[j] = d[current] + weight[current][j];
				}
			}
		}
	}
}
int  small_index()
{
	int min = INF;
	int index = 0;
	for (int i = 0; i < 4; i++) {
		if (d[i] < min && !visited[i])
		{
			min = d[i];
			index = i;
		}
	}
	return index;

}

결과

트리의 기본적인 순회방법중 전위,중위,후위순회는 코드작성이 쉽고 단순해서 이해가 쉽습니다.

(엄밀히 말해서, 쉽다기보다는 외우기쉽기 때문에)

트리의 순회의 응용으로써, 레벨(level)순회가 있습니다. 레벨순회는 루트 노드부터, 마지막 노드까지 순회하되, 왼쪽부터 오른쪽순으로 순회합니다.

트리는 사이클없는 그래프인데, 직접 트리를 그려서 bfs연산을 해보시면 알겠지만, 제가 말씀드린 왼쪽->오른쪽 순으로 가까운순으로 레벨순회를 합니다. 즉, 레벨순회는 bfs기반의 탐색(순회)방법이라고 할 수 있습니다. 

트리의 구조체를 담을 수 있는 큐를 선언하고, 큐에 루트노드를 삽입 한 후 bfs처럼 연산을 수행하면됩니다. bfs와의 차이점은 bfs는 한번 탐색한 방향은 다시 안가기 때문에, 이를 나타내기위해 visited배열을 선언하지만, 트리순회는 현재 노드의 왼쪽자식노드,오른쪽노드의 유무를 탐색하며 오직 순회만 하기때문에 상관이없습니다. 결국 한번 방문하는것은 똑같습니다.

코드를 보면 이해가 쉽습니다. 저는 트리를 담을 큐를 원형큐로 선언하였습니다.

코드

#include<cstdio>
#include<cstring>
#include<cstdlib>
typedef struct treeNode {
	char data;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;
typedef struct {
	treeNode* queue[100];
	int front, rear;
}QNode;
void level_order(treeNode*root);
void init(QNode* q)
{
	q->front = q->rear = 0;
}
int is_empty(QNode* q)
{
	return q->front == q->rear;
}
int is_full(QNode* q)
{
	return (q->rear + 1) % 100 == q->front;
}
void enqueue(QNode* q, treeNode* root)
{
	if (is_full(q))
		return;

	q->rear = (q->rear + 1) % 100;
	q->queue[q->rear] = root;
}
treeNode* dequeue(QNode* q)
{
	if (is_empty(q))
		exit(1);
	else
	{
		q->front = (q->front + 1) % 100;
		return q->queue[q->front];
	}
}
int main()
{
	treeNode ptr1 = { 'a',NULL,NULL }; treeNode ptr2 = { 'b',NULL,NULL };
	treeNode ptr3 = { 'c',NULL,NULL }; treeNode ptr4 = { 'd',NULL,NULL };
	treeNode ptr5 = { '*',&ptr1,&ptr2 }; treeNode ptr6 = { '/',&ptr3,&ptr4 };
	treeNode ptr7 = { '+',&ptr5,&ptr6 };
	treeNode* root = &ptr7;
	level_order(root);
	puts("");

}
void level_order(treeNode* root)
{
	QNode q;
	init(&q);
	if (root == NULL)return;
	enqueue(&q,root);
	while (!is_empty(&q))
	{
		root = dequeue(&q);
		printf("%c ", root->data);
		if (root->left)
			enqueue(&q, root->left);
		if (root->right)
			enqueue(&q,root->right);
	}
}

결과

자료구조의 트리 단원을 배우고 나서 응용할 수 있는 몇가지 연산들을 한 코드에 담아봤습니다.

후위 연산, 노드의 갯수, 단말노드의 갯수, 트리의높이를 구하는 코드입니다.

재귀함수를 이해하고 응용할 수 있어야함을 알 수 있습니다.

소스코드는 아래 그림과 같이 트리가 이루어져 있을 때를 가정합니다.

코드

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define max(a,b) (((a)>(b))?(a):(b))
typedef struct treeNode
{
	int data;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;

treeNode n5 = { 0,NULL,NULL };
treeNode n4 = { 1,NULL,NULL };
treeNode n3 = { 2,NULL,NULL };
treeNode n2 = { 3,&n4,&n5 };
treeNode n1 = { 4,&n2,&n3 };
treeNode* root = &n1;
int cal_post(treeNode* root)
{
	int left, right;
	if (root)
	{
		left = cal_post(root->left);
		right = cal_post(root->right);
		return root->data + left + right;
	}
	return 0;
}
int node_count(treeNode* root)
{
	int count = 0;
	if (root)
	{
		count = 1+node_count(root->left) + node_count(root->right);
	}
	return count;
}
int leaf_node(treeNode* root)
{
	int count = 0;
	if (root)
	{
		if (root->left==NULL && root->right==NULL)
		{
			return 1;
		}
		else
		{
			return leaf_node(root->left) + leaf_node(root->right);
		}
	}
	return count;
}
int height(treeNode* root)
{
	int hight = 0;
	int left, right;
	if (root)
	{
		left = height(root->left);
		right = height(root->right);
		return 1+max(left, right);
	}
	return hight;
}
int main()
{
	printf("후위덧셈!!\n%d\n", cal_post(root));
	printf("노드의갯수!!!\n%d\n", node_count(root));
	printf("단말노드의갯수!!\n%d\n", leaf_node(root));
	printf("트리의높이는!!\n%d\n", height(root));
}

결과