자료구조 실습게시판

				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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
			#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; //큐: 너비 우선 탐색(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 enqueue_loc(QueueType *q, int r, int c) {
    if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE) 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;
 
    init_queue(&q);
    here = entry;
    while (maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        maze[r][c] = '.';
        maze_print(maze);
        enqueue_loc(&q, r - 1, c);
        enqueue_loc(&q, r + 1, c);
        enqueue_loc(&q, r, c - 1);
        enqueue_loc(&q, r, c + 1);
 
        if (is_empty(&q)) {
            printf("실패\n");
            return -1;
        }
        else
            here = dequeue(&q);
    }
    printf("성공\n");
    return 0;
}
Colored by Color Scripter
			cs		