자료구조 실습게시판

[구현 방법]
- maze 크기 만큼의 이전 위치를 기억하는 배열 prev를 만들고 // element prev[MAZE_SIZE][MAZE_SIZE];
- 이동 가능 위치를 저장하는 enqueue_loc() 함수에서 이전 위치를 기억하게 한 다음 // prev[r][c] = here;
* 출구 'x' 지점에 도착하면 출구 위치로부터 prev 를 찾아가면서 역으로 출력 (순환 이용)
				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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
			#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 };
 
// 미로 탐색에 사용될 배열
element prev[MAZE_SIZE][MAZE_SIZE]; // 각 위치에 대해 이전 위치를 저장
 
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 print_path(element here) {
    if (here.r == entry.r && here.c == entry.c){
        printf("경로: ");
        return;
    }
    print_path(prev[here.r][here.c]);
    printf("(%d, %d) -> ", here.r, here.c);
}
 
void enqueue_loc(QueueType* q, element here, 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);
        prev[r][c] = here; // 이전 위치 저장
    }
}
 
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, here, r - 1, c);
        enqueue_loc(&q, here, r + 1, c);
        enqueue_loc(&q, here, r, c - 1);
        enqueue_loc(&q, here, r, c + 1);
 
        if (is_empty(&q)) {
            printf("실패\n");
            return -1;
        }
        else
            here = dequeue(&q);
    }
    print_path(here);
    printf("성공\n");
    return 0;
}
Colored by Color Scripter
			cs		