정성훈
    실습 프로그램 예)
maze.txt [3 KB]   maze2.txt [3 KB]  



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
119
120
121
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6
 
typedef struct {        // 교체!
    short r;
    short c;
} element;
 
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
} StackType;
 
// 스택 초기화 함수
void init_stack(StackType *s)
{
    s->top = -1;
}
 
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
    return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
    return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 
 
 
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(StackType *s, 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;
        push(s, 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;
    StackType s;
 
    init_stack(&s);
    here = entry;
    while (maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        maze[r][c] = '.';
        maze_print(maze);
        push_loc(&s, r - 1, c);
        push_loc(&s, r + 1, c);
        push_loc(&s, r, c - 1);
        push_loc(&s, r, c + 1);
        if (is_empty(&s)) {
            printf("실패\n");
            return;
        }
        else
            here = pop(&s);
    }
    printf("성공\n");
    return 0;
}
 cs

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6
 
typedef struct {        // 교체!
    short r;
    short c;
} element;
 
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
} StackType;
 
// 스택 초기화 함수
void init_stack(StackType *s)
{
    s->top = -1;
}
 
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
    return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
    return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 
 
 
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(StackType *s, 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;
        push(s, 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");
    }
}
 
void stack_print(StackType *s)
{
    int i;
    for (i = 5; i > s->top; i--)
        printf("|     |\n");
    for (i = s->top; i >= 0; i--)
        printf("|(%01d,%01d)|\n", s->data[i].r, s->data[i].c);
    printf("-------\n");
}
 
int main(void)
{
    int r, c;
    StackType s;
 
    init_stack(&s);
    here = entry;
    while (maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        maze[r][c] = '.';
        maze_print(maze);
        push_loc(&s, r - 1, c);
        push_loc(&s, r + 1, c);
        push_loc(&s, r, c - 1);
        push_loc(&s, r, c + 1);
 
        stack_print(&s);
        if (is_empty(&s)) {
            printf("실패\n");
            return;
        }
        else
            here = pop(&s);
    }
    printf("성공\n");
    return 0;
}
cs
  등록일 : 2020-10-05 [17:51] 조회 : 431 다운 : 294   
 
△ 이전글항목 별 우선순위를 두어서 우선순위에 따라서 처리하도록 변경 (추가)
▽ 다음글(실습 7) 미로찾기
자료구조 실습게시판
번호 ⓒ 제 목
[참고] 교재에 있는 소스코드
43 └❶ 실습 프로그램 예)
42    └❷ 실습 프로그램 예)
41       └❸ 실습 프로그램 예)
40          └❹ ⓘ큐를 이용한 너비 우선 탐색 BFS(Breadth First Search) 구현 (추가)
39             └❺ 실습 프로그램 예) 비공개
38 ⓘ(실습 6) 스택
37 └❶ 실습 프로그램 예)
36    └❷ error
35    └❷ 실습 프로그램 예)
34       └❸ 스택으로 factorial 구현 (추가)
33          └❹ 실습 프로그램 예) 비공개
32 ⓘ(실습 5) 포인터
31 └❶ 실습 프로그램 예)
30    └❷ 실습 프로그램 예)
29       └❸ 실습 프로그램 예)
28          └❹ ⓘmystrcmp() 함수의 구현 (추가)
27             └❺ 실습 프로그램 예) 비공개
26 ⓘ(실습 4) 동적 메모리할당
25 └❶ 실습 프로그램 예)
24    └❷ 실습 프로그램 예)

[1][2][3][4]