CH 14 - 2 그래프의 탐색

honeyricecake·2022년 3월 5일

BFS DFS c언어 그래프 자료구조 탐색

자료구조

목록 보기

35/36

이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.

Prologue

탐색에는 깊이 우선 탐색, 너비 우선 탐색이 있다.
그래프하면 탐색이 우선인데, 이 이슈는 사실 Search의 이슈가 아니고 모든 정점을 돌아다니는 것이다.

그런데 기존의 자료구조에는 구조라는 틀이 있었고, 그 구조를 근거로 탐색을 할 수 있었는데
그래프는 정해진 구조가 없어서 그것이 불가능하다.

1. 깊이 우선 탐색 (Depth First Search)

쉽게 말해서 계속 한 지점에서 계속 파고 들어가는 것을 깊이 우선 탐색이라 한다.

결국 위의 과정을 취하면 start로 돌아와서 start에서 연락을 취할 곳이 없으면 끝.

Tip.동수에게 연결된 간선이 하나 뿐인 또 하나의 정점이 있다고 간주해보자.
그러면 동수에서 시작했을 때, 동수로 돌아와서 그 정점으로 갔다가 다시 동수에게 가서 끝날 것이다.

즉, 동수가 연락을 마지막으로 받고 연락할 사람이 없을 때, 깊이 우선 탐색이 끝났음을 알 수 있다.

2. 너비 우선 탐색 (Breadth First Search)

연결되어 있는 모든 정점을 탐색하고 그 다음 정점으로 이동하고 이를 반복
두번째에서 민석이 먼저인지 동수가 먼저인지는 상관없다.

3. 구현의 원리

깊이 우선 탐색 - 스텍을 활용한다는데 나는 재귀함수를 활용해야겠다.
너비 우선 탐색 - 큐를 활용한다고 한다. 아마 탐색된 정점을 큐에 넣고 그 다음 쿠의 맨위 에 있는 정점을 기준으로 연결된 정점들을 탐색하는 과정을 반복하겠지.

이를 바탕으로 그냥 직접 백준 문제를 풀어봐야겠다.

4. DFS와 BFS

https://www.acmicpc.net/problem/1260

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

char array[1001][1001];

typedef struct queue
{
	int top;
	int entrance;
	int arr[1000];
}Queue;

Queue queue;

void DFS(int N, int start)
{
	int i;
	array[start][0] = 1;
	printf("%d ", start);
	for (i = 1; i <= N; i++)
	{
		if (array[start][i])
		{
			if (array[i][0] == 0)
			{
				DFS(N, i);
			}
		}
	}
	return;
}

void BFS(int N, int start, Queue* pq)
{
	int i;

	if (pq->top >= N - 1) return;

	for (i = 1; i <= N; i++)
	{
		if (array[start][i])
		{
			if (array[i][0])
			{
				array[i][0] = 0;
				printf("%d ", i);
				pq->arr[pq->entrance] = i;
				pq->entrance++;
			}
		}
	}
	BFS(N, pq->arr[pq->top++], pq);
	return;
}

int main()
{
	int i;
	int N, M, start;
	int x, y;
	scanf("%d %d %d", &N, &M, &start);

	for (i = 0; i < M; i++)
	{
		scanf("%d %d", &x, &y);
		array[x][y] = 1;
		array[y][x] = 1;
	}

	DFS(N, start);

	printf("\n");

	Queue* pq = &queue;
	
	pq->top = 0;
	pq->entrance = 0;

	printf("%d ", start);
	array[start][0] = 0;
	BFS(N, start, pq);

	return 0;
}