이동 할 수 있는 곳을 스택에 저장해놓고 사용하면 깊이 우선 탐색 DFS(Depth First Search)가 된다.
교재 프로그램은 스택을 사용한 DFS 방법이다.
이를 큐를 이용한 너비 우선 탐색 BFS 로 구현하시오.
(BFS로 구현하면 최단경로를 찾을 수 있음)
- push_loc() 함수를 enqueue_loc() 함수로
- pop() 함수를 dequeue() 함수로 구현
| DFS | BFS |
 |  |
[큐 구현 방법 참고]
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAZE_SIZE 6 #define QUEUE_SIZE 100 typedef struct { short r; short c; } element; typedef struct { element data[QUEUE_SIZE]; int front, rear; } QueueType; // 큐 초기화 함수 void init_queue(QueueType *q) { q->front = q->rear = 0; } // 큐 공백 상태 검출 함수 int is_empty(QueueType *q) { return (q->front == q->rear); } // 큐 포화 상태 검출 함수 int is_full(QueueType *q) { return ((q->rear + 1) % QUEUE_SIZE == q->front); } // 큐에 삽입하는 함수 void enqueue(QueueType *q, element item) { if (is_full(q)) { fprintf(stderr, "큐 포화 에러\n"); return; } q->rear = (q->rear + 1) % QUEUE_SIZE; q->data[q->rear] = item; } // 큐에서 삭제하는 함수 element dequeue(QueueType *q) { if (is_empty(q)) { fprintf(stderr, "큐 공백 에러\n"); exit(1); } q->front = (q->front + 1) % QUEUE_SIZE; return q->data[q->front]; } | cs |
자료구조 실습게시판