스택을 이용한 미로찾기입니다.

원리는 매우 간단합니다.

일단 가본 길을 전부 스택에 쌓고 갈수 있는 공간이 없으면

스택의 데이터를 POP하고 위에 작업을 계속 진행합니다.

길이냐 벽이냐는 원핫코딩으로 코딩하였습니다.

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
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define WIDTH 10
#define HIGH 10
char map[HIGH][WIDTH] = {
   { 1111111111 },
   { –1, 000000011 },
   { 1111110111 },
   { 1111110111 },
   { 1100000111 },
   { 1101110111 },
   { 1101110111 },
   { 1101110001 },
   { 1121110111 },
   { 1111111111 }
};
void display(){
   int i, j;
   for (i = 0; i < HIGH; ++i){
      for (j = 0; j < WIDTH; ++j){
         switch (map[i][j]){
         case –1:
            printf(“◇”);
            break;
         case 1:
            printf(“■”);
            break;
         case 2:
            printf(“★”);
            break;
         case 0:
            printf(“□”);
         }
      }
      printf(“\n”);
   }
}
typedef struct __POINT
{
   int y;
   int x;
}point;
typedef struct __STACK
{
   struct __STACK * link;
   point point;
}stack;
void init(stack ** p_head){
   *p_head = NULL;
}
void push(stack **p_head, point point){
   stack * temp = (stack*)malloc(sizeof(stack));
   if (!temp)
      exit(1);
   if (*p_head != NULL){
      temp–>point = point;
      temp–>link = *p_head;
   }
   else{
      temp–>point = point;
      temp–>link = NULL;
   }
   *p_head = temp;
}
point pop(stack **p_head){
   if (!p_head)
      exit(1);
   point point_temp = (*p_head)–>point;
   stack * stack_temp = *p_head;
   *p_head = (*p_head)–>link;
   free(stack_temp);
   return point_temp;
}
void show(stack* head){
   for (; head; head = head–>link)
      printf(“(%d %d)\n”, head–>point.x, head–>point.y);
}
bool stackfree(stack **  p_head){
   stack * q = *p_head;
   stack * p =   NULL;
   if (!p_head)
      return false;
   for (; q; p = q, q = q–>link){
      free(p);
   }
   *p_head = NULL;
}
int main(){
   point Location=1,0 };
   stack *head;
   init(&head);
   push(&head,Location);
   while (map[Location.y + 1][Location.x]!=2){
      map[Location.y][Location.x] = –1;
      display();
      show(head);
      //UP
      if (map[Location.y + 1][Location.x] != 1 && map[Location.y+1 ][Location.x] !=–1 ){
         Location.y++;
         push(&head, Location);
      }
      //DOWN
      else if (map[Location.y – 1][Location.x] != 1 && map[Location.y–1][Location.x] != –1){
         Location.y––;
         push(&head, Location);
      }
      //LEFT
      else if (map[Location.y][Location.x – 1!= 1 && map[Location.y][Location.x–1] != –1){
         Location.x––;
         push(&head, Location);
      }
      //RIGHT
      else if (map[Location.y][Location.x + 1!= 1 && map[Location.y][Location.x+1!= –1){
         Location.x++;
         push(&head, Location);
      }
      //실패시 
      else{
         Location = pop(&head);
      }
      system(“pause”);
      system(“cls”);
   }
   printf(“목적지 도착”);
   display();
   stackfree(&head);
}
cs
카테고리: algorithm

1개의 댓글

Сialis · 2018년 11월 8일 5:47 오후

Its such as you learn my mind! You seem to grasp a lot about this,
such as you wrote the book in it or something. I believe that you simply
can do with some p.c. to pressure the message home a bit, but instead of
that, this is wonderful blog. A great read. I’ll definitely be back.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다