학생실습 게시판

//너비 우선 탐색.c#include #include #include #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; //큐: 너비 우선 탐색(BFS), 스택: 깊이 우선 탐색(DFS)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];}element here = { 1,0 }, entry = { 1,0 };char maze[MAZE_SIZE][MAZE_SIZE] = { { '1', '1', '1', '1', '1', '1' }, { 'e', '0', '1', '0', '0', '1' }, { '1', '0', '0', '0', '1', '1' }, { '1', '0', '1', '0', '1', '1' }, { '1', '0', '1', '0', '0', 'x' }, { '1', '1', '1', '1', '1', '1' }};void push_loc(QueueType *q, int r, int c) { if (r < 0 || c < 0) return; if (maze[r][c] != '1' && maze[r][c] != '.') { element tmp; tmp.r = r; tmp.c = c; enqueue(q, tmp); }}void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) { printf("\n"); for (int r = 0; r < MAZE_SIZE; r++) { for (int c = 0; c < MAZE_SIZE; c++) { printf("%c", maze[r][c]); } printf("\n"); }}int main(void) { int r, c; QueueType q, qm; init_queue(&q); init_queue(&qm); here = entry; while (maze[here.r][here.c] != 'x') { r = here.r; c = here.c; maze[r][c] = '.'; maze_print(maze); push_loc(&q, r - 1, c); push_loc(&q, r + 1, c); push_loc(&q, r, c - 1); push_loc(&q, r, c + 1); if (is_empty(&q)) { printf("실패\n"); return -1; } else here = dequeue(&q); } printf("성공\n"); return 0;}