힙 정렬(Heap Sort)


정렬 시리즈 중 고급 정렬 알고리즘에 속하는 힙정렬은 힙이라는 자료구조를 토대로 정렬합니다. 그러니까 힙에 대해서 알고 와야겠죠??


힙에 대해서 모르는 분들은 아래 url를 참고하시기 바랄게요.

https://reakwon.tistory.com/42


힙에 대해서 아셨다면 이제 어떻게 정렬을 하는지 알아보도록 하지요.


정렬


위의 url의 코드를 통해서 힙정렬을 한다고 하면 의외로 쉽습니다. 메인 함수를 이렇게 바꾸어서 실행해보세요. 정렬이 아주아주 잘됩니다.


int main() {
	heap hp;
	initHeap(&hp);
	int i;
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	for (i = 0; i < size; i++)
		insert(&hp, arr[i]);

	for (i = 0; i < size; i++)
		arr[i] = deleteData(&hp);

	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}


근데 문제점이 있죠. arr이라는 배열 공간과 heap이라는 배열 공간 두개를 쓰니까 메모리의 낭비가 있습니다.


그리고 insert함수를 부르는 시간 nlog(n), deleteData함수를 부르는 시간 nlog(n)입니다.


우리는 더 잘할 수 있다

이것도 훌륭하지만 우리는 더 나아갈 수 있습니다. 더 잘할 수 있습니다.


아래의 그림은 방금 위의 배열을 단지 트리 형태로 표현한 것입니다.




최대힙을 구현할 것인데, 힙의 조건을 만족하지 않지요. 왜냐면 5가 가장 큰 원소가 아니거든요. 


아차, heap을 구현할때는 1부터 인덱스가 시작되는데 힙정렬할땐 0부터 시작한답니다. 왜냐면 공간을 아끼기 위해 그 배열 자체를 정렬할 것이기 때문이에요. 배열의 인덱스는 0부터 시작하는 것이니까요.


heapify

우리는 이것을 힙의 모양으로 고치는 것, 그 함수를 heapify라고 정의해보겠습니다.


heapify(int arr[], int here, int size) = 크기가 size인 배열 arr을 here부터 힙의 모양대로 만드는 함수


코드와 함께 heapify가 어떻게 동작하는 지 보도록 합시다.



void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left<size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}


이 함수 하나로 힙의 모양을 만들수는 없습니다. 

아래 왼쪽의 트리에서 우리가 heapify(arr, 0, size)를 호출한다고 치면 오른쪽의 트리로 만들어지게 됩니다.




가장 작은 1이 맨 끝에 이동함을 알 수 있죠. 하지만 최대힙은 아닙니다. 4가 가장 큰 값이 아니잖아요. 


우리는 이렇게 생각해볼 수 있습니다. 만약 자식을 갖고 있는 노드가 있다면 그 위치에서부터 heapify를  역순으로 호출하는 방식이죠. 그러니까 자식노드를 갖고 있는 노드는 0, 1, 2의 인덱스인데, heapify(arr, 2, size), heapify(arr, 1, size), heapify(arr, 0, size) 이렇게 호출하면 되지 않을까요?




그런 함수가 buildHeap이라는 함수입니다.


buildHeap


우선 우리는 자식을 갖고 있는 노드가 어떤 인덱스를 갖고 있어야하는지 알아야합니다. 어떻게 알 수 있을까요??


가장 마지막 노드는 size-1의 노드인것을 알 수 있습니다. 하지만 우리는 그 부모님 성함을 알 수 있죠. 바로 size/2 -1이 그 부모노드의 인덱스라는 것을 알 수 있습니다.

그러니까 맨 마지막의 인덱스는 5, 그 부모노드는 5/2 -1로 2가 됩니다. 


이제부터 우리는 

{ 5,3,4,1,6,10 }

이 배열을 heap으로 만드는 과정을 살펴봅니다.


초기는 아래와 같죠.




자식을 갖고 있는 노드를 알았으니 heapify(arr, 2, size)를 호출해봅시다. 그러면 위의 트리는 이렇게 바뀝니다.





10이 더 크니까 4와 자리를 바꾸죠.


이제 heapify(arr, 1, size)를 호출하면 다음과 같이 바뀝니다.




6이 더 크니까 3과 자리를 바꿉니다.


이제 heapify(arr,  0, size)를 호출합시다.



5의 자식 중 10이 5보다 크네요. 자리 바꿔줍니다.


루트까지 호출이 되었으니까 heapify는 종료됩니다.


어때요? 최대힙 모양이 완성되었죠? 

이것을 for루프로 돌리면 아래와 같은 코드가 됩니다.


void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}




이제 정렬 좀 하자..

여기까지 됐으면 거의 끝났습니다. 루트원소를 맨끝에 옮기고 다시 heapify를 호출하면 됩니다. 단, 트리의 사이즈는 하나씩 줄어듭니다.


이제 정렬과정만 보이면 되겠군요.


void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}

트리의 크기가 처음에는 6입니다. 크기를 점점 줄여나가는 것을 보세요. 

아래의 그림들이 위의 코드가 어떻게 동작하는지 보여줍니다.




우선 0번 노드와 5번 노드의 값을 바꾸어줍니다. 똥색 표시는 이미 정렬된 부분을 의

미합니다. 그 후 heapify를 호출하면 다시 힙의 모양을 유지하게 됩니다. 




이제는 0번 노드와 4번 노드를 교환합니다. 그리고 똥색으로 표시해주고, 이제는 트리 사이즈가 4가 됩니다. 그 후 heapify를 호출해서 사이즈 4까지 힙의 모양으로 만들어 줍니다. 5가 제일 큰 노드가 되겠네요.



이제 0번 노드와 3번 노드를 바꿉니다. 5, 6, 10까지 정렬된 것이 보이죠?? 그 후 heapify를 호출해서 최대힙의 모양으로 유지합니다.




이제 거의 다 왔습니다. 0번 노드가 가장 크므로 마지막 노드와 교체합니다. 4까지 정렬된 것을 확인할 수 있습니다. 그 후 heapify 호출해서 heap으로 유지합니다.



이제 가장 큰 노드 0번과 1번을 바꿉니다. 3까지 정렬됐습니다. 그 후 heapify호출하여 heap의 모양으로 만들어 줍니다.





이제 하나남았네요. 가장 큰 노드가 자기 자신이니까 바꾸나 마나고 heapify를 호출해도 그 모양 그대로 유지합니다.

트리를 보세요! 정렬이 된것을 확인할 수 있지요??




여기 그 전체코드가 있습니다.



#include <stdio.h>

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left < size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}

void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}

void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}
void printArray(int arr[], int size) {
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main() {
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	
	heapSort(arr, size);
	printArray(arr, size);
}


시간복잡도

힙 정렬에서 시간 복잡도는 O(nlogn)입니다. 완전 이진 트리이기때문에 높이가 균등합니다. 그래서 heapify는 logn으로 보장할 수 있습니다. 그리고 heapify를 n번 호출하기 때문에 nlogn이라는 것을 알 수 있지요. 


도움이 되셨나요??

반응형
블로그 이미지

REAKWON

와나진짜

,

동전 교환 알고리즘


개념


편의점 아르바이트생인 A는 야간에 편의점 알바를 하고 있어요. 막상 편의점에 도착해서 보니까 동전이 없습니다. 그래서 사장님께 전화를 걸었으나, 이미 술취해서 뻗어버린 상태입니다. 할 수 없이 일단 가지고 있는 동전으로 거스름돈을 주며 내일 아침 사장님이 올때까지 뻐겨야하는 상황이 발생했습니다.

그러기 위해서는 거스름돈에 사용되는 동전의 갯수를 최소로 사용하여 주어야하는데 어떻게 최소 동전 갯수를 구할 수 있을까요?


현실에서는 10원, 50원, 100원, 500원의 동전이 있지만 여기서는 1, 4, 5, 6원의 동전이 있다고 가정하도록 하겠습니다. 만약 23원의 거스름돈을 위의 동전을 최소로 사용해 거슬러준다면 어떻게 거슬러주면 될까요? 여러가지가 있지만, 우선 가장 큰 값인 6을 먼저주고 남은것은 그 다음 큰 동전으로 사용한다면 6원 3개, 5원 1개로 23원을 만들 수 있습니다. 동전을 최소로 사용해서 준 것 맞습니까?




네, 가장 최소의 동전을 사용해서 준 것이 맞습니다.

항상 최대값의 동전을 우선적으로 사용해서 얻은 결과가 바로 답일까요? 일리있어 보이지만 항상 그렇지 않습니다.


14원을 예로 한번 들어보도록 합시다.

위의 방식대로 한다면 6원 2개, 1원 2개, 4개의 동전을 사용해서 14원을 만들 수 있습니다.

하지만 5원부터 주게되면 5원 2개, 4원 1개로 3개의 동전을 사용해서 14원을 만들 수 있습니다.


이제부터 어떻게 구할지 생각해보도록 하겠습니다.

우선 동전 하나를 가지고 얼마를 만들 수 있을지 생각합시다. 우선 1원입니다. 1원은 모든 수를 전부 만들 수 있습니다. 그렇다면 아래의 표와 같겠네요.


1원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 4(4,0,0,0)

 5

 5(5,0,0,0)

 6

 6(6,0,0,0)

 7

 7(7,0,0,0)

 8

 8(8,0,0,0)

 9

 9(9,0,0,0)

 10

 10(10,0,0,0)

 11

 11(11,0,0,0)

 12

 12(12,0,0,0)

 13

 13(13,0,0,0)

 14

 14(14,0,0,0)



4원을 사용한다면 4원은 당연히 한개로 만들 수 있고, 5원은 그 전의 1원과 합쳐서 만들 수 있습니다. 그렇다면 5원은 2개로 만들 수 있겠군요. 8원은 그전의 4원 2개로 만들 수 있습니다.

9원은 어떻겠습니까? 그전에 5원을 2개의 동전으로 구했었습니다. 1원과 4원을 합쳐서 말입니다. 여기에 4원을 더 얹으면 9원 아닌가요? 그래서 1원 1개, 4원 2개로 9원을 만들 수 있습니다. 그렇다면 표가 다음과 같이 바뀝니다.


4원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 2(1,1,0,0)

 6

 3(2,1,0,0)

 7

 4(3,1,0,0)

 8

 2(0,2,0,0)

 9

 3(1,2,0,0)

 10

 4(2,2,0,0)

 11

 5(3,2,0,0)

 12

 3(0,3,0,0)

 13

 4(1,3,0,0)

 14

 5(2,3,0,0)



이제 5원을 사용하도록 합시다. 5원을 사용하게 되면 5원은 동전 한개로 만들 수 있고, 6원은 1원의 동전화 합쳐서 만들 수 있겠습니다. 10원은 5원 두개로 만들 수 있고 11원이 그 전의 6원을 만들었던 것에서 5원을 추가하여 만들 수 있답니다. 




5원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)  

 1

 1(1,0,0,0)

 2

 2(1,0,0,0)

 3

 3(1,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 2(1,0,1,0)

 7

 3(2,0,1,0)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 3(1,0,2,0)

 12

 3(0,3,0,0)

 13

 3(0,2,1,0)

 14

 3(0,1,2,0)


이제 감이 오시나요?


결국 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드니까 그 전의 거스름돈에 1을 더하면 됩니다. 

하지만 이미 구해진 거스름돈이 더 적은값을 가지고 있다면 현재의 값을 유지하면 되는 것입니다. 그래서 이런 식이 나오게 됩니다.


dp[j] = MIN(dp[j], dp[j - coin[i]] + 1); 


dp[j]는 현재 구할 거스름돈의 값입니다. 그래서 현재 거스름돈에서 현재 동전을 뺀 값이 dp[j-coin[i]]를 의미합니다. 그래서 현재 거스름돈 dp[j]와dp[j-coin[i]]+1을 비교하여 작은 값이 답이 됩니다.


이제 5도 했으니 6도 해봅시다. 위의 식대로 구한다면 다음의 표가 완성되겠습니다.


6원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)   

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 1(0,0,0,1)

 7

 2(1,0,0,1)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 2(0,0,1,1)

 12

 2(0,0,0,2)

 13

 3(1,0,0,2)

 14

 3(0,1,2,0)



이제 모든 동전을 사용해서 14원이 3개의 동전으로 교환될 수 있다는 것을 알았습니다.




구현

구현은 뭐 위에서 설명한 것을 그대로 코드로 옮기면 되는데 몇몇 설명할게 아직은 남아있습니다. 전체 소스코드를 보면서 이야기 해보도록 하겠습니다.

#include <stdio.h>
#define MIN(a,b) a<b ? a:b
#define N 4
#define M 14
#define INF 987654321;
int dp[M+1];
int coin[N] = { 1,4,5,6 };
int main() {
	int i, j;

	for (i = 1; i <= M; i++)
		dp[i] = INF;

	for (i = 0; i < N; i++) {
		printf("동전 %d 사용시\n",coin[i]);
		for (j = coin[i]; j <= M; j++) {
			dp[j] = MIN(dp[j], dp[j - coin[i]] + 1);
			printf("%d %d\n", j, dp[j]);
		}
		printf("\n\n");
	}
	printf("%d\n", dp[M]);
}




우선 dp를 아주 큰 값으로 초기에 설정합니다. 그렇지 않으면 0이 되니까요. MIN 매크로 함수를 통해서 작은 값을 구해야하는데 dp가 0이 되버리면 MIN은 항상 0을 반환하게 됩니다.
위에서 이야기한대로 코드로 옮겼습니다.


반응형
블로그 이미지

REAKWON

와나진짜

,

BOJ [1260] DFS와 BFS



문제해석


그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.


제약조건


간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.


문제풀이



DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.


DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867





코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.



반응형
블로그 이미지

REAKWON

와나진짜

,

1012번 유기농 배추



문제 해석


문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.



그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.


위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.




이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.


제약 조건


테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.


최대 50*50이 주어질 수가 있겠군요. 



풀이


이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.



현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.


하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.


따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?





#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

		memset(map, 0, sizeof(map));

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}


이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?



아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.




dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.






이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.


답은 위 코드의 count로 표현됩니다.


시간 복잡도는 N*M이 됩니다. 


이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.


BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.


또 어떤 방법으로 풀 수 있을까요??




반응형
블로그 이미지

REAKWON

와나진짜

,

BFS(Breadth First Search, 너비우선탐색)


그래프 이론 DFS와 BFS 중 BFS는 그래프를 가까운 정점부터 순서대로 탐색하는 그래프 탐색 알고리즘이랍니다. 그래프에서 탐색 시 아주 많이 사용되는 탐색기법이지요. 우선 다음과 같은 무향그래프가 있다고 가정해보겠습니다. 


우선 그래프 탐색을 하기 전에 조건이 있습니다.

1. 처음 정점 0부터 시작한다고 칩시다.

2. 정점을 방문한 적이 있다면 다시 방문하지 않는다.

3. 방문해야 할 정점이 여러 개일 경우 가장 번호가 낮은 정점부터 방문한다.




BFS로 위 그래프를 탐색하는 과정을 보겠습니다 


1. 0을 방문한다.

2. 0과 가장 가까운 정점을 찾는다 ( 1, 5, 6).

3. 1이 방문되지 않았으므로 1을 방문한다.

4. 5가 방문되지 않았으므로 5를 방문한다.

5. 6이 방문되지 않았으므로 6을 방문한다.

6. 1에서 가장 가까운 정점을 찾는다 (0, 2, 3).

7. 0은 이미 방문했으므로 skip한다.

8. 2는 방문되지 않았으므로 2를 방문한다.

9. 3이 방문되지 않았으므로 3을 방문한다.

10. 5에서 가장 가까운 정점을 찾는다 (0, 6).

11. 0과 6은 방문됐으므로 skip한다.

12. 6과 가장 가까운 정점을 찾는다 (0, 5).

13. 0과 5는 이미 방문됐으므로 skip한다.

14. 2와 가장 가까운 정점을 찾는다 (1, 4). 

15. 1은 이미 방문됐으므로 skip한다.

16. 4는 방문되지 않았으므로 4를 방문한다.

17. 모든 정점을 지나쳤으므로 종료한다.


이제 방문된 점을 차례대로 나열해본다면  0 - 1 - 5 - 6 - 2 - 3 - 4 로 방문이 되는 것을 확인 할 수 있습니다. 코드로 표현하면 어떻게 될까요? 아래 C++ 소스코드로 BFS를 구현해보았습니다.


#include <cstdio> #include <vector> #include <queue> #define V 7 using namespace std; int g[V][V] = { {0,1,0,0,0,1,1}, {1,0,1,1,0,0,0}, {0,1,0,0,1,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {1,0,0,0,0,0,1}, {1,0,0,0,0,1,0} }; vector

bfs(int start) { vector discovered(V, false); queue next; vector order; visited[start] = true; next.push(start); while (!next.empty()) { int from = next.front(); next.pop(); order.push_back(from); for (int to = 0; to < V; to++) { if (g[from][to] == 1 && !visited[to]) { next.push(to); visited[to] = true; } } } return order; } int main() { vector bfsOrder = bfs(0); for (int i = 0; i < V; i++) printf("%d ", bfsOrder[i]); }


이 코드가 어떻게 동작이 되는 지 하나하나 살펴봅시다. 그 전에 준비물이 있습니다. 바로 자료구조 큐를 준비해야 된다는 겁니다. 큐를 통해서 어떻게 BFS가 구현될까요? 다음과 같이 하늘색 상자는 큐를 나타낸다고 하겠습니다. 0부터 노드가 방문되기 때문에 큐 안에는 0이 저장되어 있습니다.



이 후 0은 방문될때 큐에서 꺼내어 집니다. 그 다음에 0에서 가장 가까운 정점 중에 방문되지 않은 정점을 큐에 저장합니다. 이렇게 말입니다.


0을 방문합니다. 0은 큐에서 꺼내어 지고 0과 가장 가까운 정점 1 5 6이 큐에 저장됐습니다. 그 후에는 다시 1을 큐에서 꺼내오고 1과 가장 가까운 정점을 큐에 집어 넣습니다.

단, 방문되지 않은 녀석들로요.



1은 방문이 되어 큐에서 나오고 2와 3이 추가 돼었군요. 역시 과정은 계속 반복됩니다. 다음 5가 방문될 차례입니다. 5를 꺼내고 5와 가장 가까운 정점을 추가합니다.



5와 가장 가까운 정점 0과 6이 있는데, 6은 아직 큐에 존재하니까 방문하지 않은 걸로 간주합니다. 그래서 6을 다시 큐에 집어 넣습니다. 다음 6을 방문합니다. 



6과 가장 가까운 정점 0과 5는 이미 방문된 상태랍니다. 그래서 큐에 집어 넣지 않습니다. 다음 2를 방문합니다. 





2과 가장 가까운 정점은 1, 4로 1은 이미 방문된 상태로 넘어가고 4는 큐에 들어갑니다. 왜냐면 방문될 정점으로 큐에 아직 존재하니까요. 다음 3을 방문합니다.


3과 가장 가까운 정점 1은 이미 방문된 상태라 넘어갑니다. 다음 4를 방문합니다.

4와 가장 가까운 정점 2는 이미 큐에서 나와 방문이 되었습니다. 어느 정점하나 큐에 들어가지 않습니다. 이제 큐에 남아있는 방문될 정점 6과 4는 이미 방문이 되었으므로 큐에서 그냥 빠져나옵니다. 방문되지 않는 다는 뜻입니다. 버립니다.


이로써 큐는 모두 비워졌습니다. 큐가 비워졌으니 더 이상 방문할 정점이 없으니 BFS과정은 끝나게 됩니다. 이로써 BFS가 어떻게 동작하는 지 살펴보았습니다. BFS는 그럼 도대체 언제 사용하게 될까요? 그건 다음에 알아보도록 하겠습니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

DFS(Depth First Search : 깊이 우선 탐색)


그래프, 어렵습니다. 그래프에 대한 이론은 많은 걸로 알고 있습니다. 그중에서 대표적인 것이 바로 탐색 기법인데요. DFSBFS라는 녀석, 이 둘이 가장 대표적입니다. 먼저 DFS(Depth First Search)라고 하는 놈이 있어요. 깊이 우선 탐색이라고 우리는 말하더군요! 이런 거는 역시 그림으로 한 방에 이해를 해버리는 게 좋거든요? 그래서 제가 그림을 하나 준비해왔답니다. 아래와 같은 무향그래프가 있다고 칩시다! 0에서부터 시작해서 모든 정점을 방문하려고 합니다. DFS탐색기법을 사용해서 정점을 방문할때 어떤 순서로 방문하게 될까요?

단, 규칙은 작은 노드순으로 방문한다는 조건으로요



이름답게 그 정점에서 아주 깊숙히 들어갑니다. 들어가서 더 이상 들어 갈 곳 없을 때까지 깊숙히 말입니다. 하지만 이미 방문된 노드라면 그 노드는 다시 방문하지 않습니다. 그럼 이제부터 탐색을 시작해 보겠습니다.




0에서부터 시작해서 노드번호가 작은 순으로 가려면 1을 방문해야겠지요?? 1과 인접한 가장 작은 노드 번호를 갖고 아직 방문하지 않은 노드는 2가 있네요. 2와 인접한 노드 중 가장 작고 방문하지 않은 노드는 4가 있습니다. 4는 더 이상 갈 곳이 없으므로 다시 돌아옵니다.


이제 3을 방문할 차례입니다. 1에 인접한 노드는 23이었는 데 방금 2쪽 노드를 모두 방문했으니까요. 3은 인접한 노드가 1이 있는 데 이미 방문을 했답니다.


1로 다시 돌아와서 그 다음으로 인접한 노드를 찾아봅시다. 5가 있네요. 5에서 인접한 노드 중 방문하지 않고 가장 작은 노드는 6이 있습니다. 6은 이제 마지막 노드가 되겠습니다. 왜냐면 0도 방문했고 5도 방문했으니까요.


이것으로 모두 방문을 해보았습니다. 순서는 0 - 1 - 2 - 4 - 3 - 5 - 6 이렇게 되겠네요.

그림을 그려보면 이런 순서랍니다.


그렇다면 다음은 DFS를 코드로 구현해볼까요? 우리는 g라는 2차원 배열 변수로 그래프를 표현하게 됩니다. 바로 위와 같은 그래프입니다. 그리고 한가지 더 말씀드리자면 visited라는 변수를 통해서 그 정점이 방문이 되었는지 기록합니다. 이미 방문이 되면 더 이상 그 정점을 방문하면 안되니까요.


c 소스코드는 바로 아래와 같답니다.




#include <stdio.h>

#define N 7

int g[N][N]=
{
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0}, 
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};
int visited[N];
void dfs(int here) {

	//지금 here이 이미 방문된 정점이라면 다시 빠꾸
	if (visited[here]) return;

	printf("정점 %d를 방문\n", here);

	visited[here] = 1;	//지금 here 정점은 방문

	for (int next = 0; next < N; next++) 
		//그래프가 이어져있으면서, 아직 다음 정점이 방문되지 않았으면 ㄱㄱ
		if (g[here][next] == 1 && !visited[next]) dfs(next);
}
int main() {
	dfs(0);
}



결과는 이렇습니다.



네, 뭐 간단합니다. 재귀함수로 dfs를 쉽게 구현해볼 수 있습니다. 그렇다면 dfs를 도대체 어디에 활용할 수 있을까요? 배웠으면 써먹어야 될꺼 아니겠어요? 그런 다음 포스팅에 알아보도록 하겠습니다.



반응형
블로그 이미지

REAKWON

와나진짜

,