BFS, DFS 알고리즘

 

내가 BFS와 DFS를 배운 이유

---

저번에 c++ 프로젝트를 진행하면서 가장 문제였던 부분은 '플레이어를 따라오는 적'이었다.(c++로 게임 제작)

나는 자료구조와 알고리즘을 배우기는 했지만 이해를 했다고는 할 수 없는 상태였다.

그랬기 때문에 그 문제를 해결하지 못했었다.

 

하지만 후에 다시 자료구조와 알고리즘을 공부하기 시작했다.

c#으로 게임 만드는 강의를 보면서 BFS와 DFS를 배웠다. 다익스트라 최단경로 알고리즘도 배웠다.

그러면서 이것으로 나의 문제를 해결할 수 있겠다는 생각이 들었다.

 

일단 나는 적이 대각선으로 움직이지도 않고 간선에 가중치가 필요 없어서 DFS 알고리즘을 사용하였다.

그리고 어제 그 문제를 해결했다!!😋😁

 

나중에 되면 그 문제를 해결한 내용의 글을 써 볼 예정이다!

 

백준 문제 1260번_DFS와 BFS

---

아무튼 오늘은 백준문제 1260번 "DFS와 BFS"문제를 풀고 쓰는 글이다.

 

풀었다!

 

근데 쓸데없이 길게 코드를 짠듯하다.

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

void DFS(int** matrix, int len, bool* visited, int now);
void BFS(int** matrix, int len, int start);

int main() {

	//정점 번호가 작은 것을 먼저 방문.

	int N; //정점의 개수
	int M; //간선의 개수
	int V; //탐색 시작할 정점의 번호
	int t1, t2;

	scanf("%d%d%d", &N, &M, &V);
	int** Matrix = (int**)malloc(sizeof(int*) * N);

	for (int i = 0; i < N; i++) {
		Matrix[i] = (int*)malloc(sizeof(int) * N);
		for (int j = 0; j < N; j++) {
			Matrix[i][j] = -1;
		}
	}

	//간선이 연결하는 두 정점의 번호
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &t1, &t2);
		Matrix[t1 - 1][t2 - 1] = t2;
		Matrix[t2 - 1][t1 - 1] = t1;
	}

	//정점 번호가 작은 것을 먼저 방문

	//DFS 수행 결과
	bool* visited = (bool*)malloc(sizeof(bool) * N);
	for (int i = 0; i < N; i++) {
		visited[i] = false;
	}
	DFS(Matrix, N, visited, V);

	printf("\n");
	//BFS 수행 결과
	BFS(Matrix, N, V);

	free(Matrix[0]);
	free(Matrix);
	return 0;
}

void DFS(int** matrix, int len, bool* visited, int now) {

	visited[now - 1] = true;
	printf("%d ", now);

	for (int next = 0; next < len; next++) {
		if (visited[next]) { continue; }
		if (matrix[now - 1][next] == -1) { continue; }
		DFS(matrix, len, visited, next+1);
	}
}

struct queue {
	int data[10000];
	int front;
	int rear;
};

void EnQueue(struct queue* q, int data) {
	q->data[q->rear] = data;
	q->rear++;
}

int DeQueue(struct queue* q) {
	return q->data[q->front++];
}


void BFS(int** matrix, int len, int start) {
	int now;

	bool* found = (bool*)malloc(sizeof(bool) * len);
	for (int i = 0; i < len; i++) { found[i] = false; }
	struct queue q;
	q.front = 0; q.rear = 0;

	EnQueue(&q, start - 1); //인덱스로 저장
	found[start - 1] = true;

	while(q.rear != q.front) {
		now = DeQueue(&q);
		printf("%d ", now+1);

		for (int next = 0; next < len; next++) {
			if (found[next]) { continue; }
			if (matrix[now][next] == -1) { continue; }
			EnQueue(&q, next);
			found[next] = true;
		}

	}

}

어후... ㅎㅎ

 

다른 사람의 코드를 보니 그냥 동적 배열을 생성하는 것이 아닌 미리 배열을 잡아놓고 사용하였다.

그 방법도 좋은 것 같다.

 

또 BFS의 코드도 더 짧은 것 같았다. 다음에 다시 보면서 짧게 줄일 수 있는 방법을 생각해봐야겠다.

 

후기

---

인덱스를 주의하자!

뿌듯하다!