[C / 자료구조] 3주차 과제 - 미로 문제

미로 문제 

 

main

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#define WALL '1'
#define ROAD '0'


#define PATH '#'
#define GOAL 'G'
#define VISITED '.'
#define MAX_SIZE 20

char maze[MAX_SIZE][MAX_SIZE];
int maze_size = 0;

void init_maze() {
    printf("Maze Size >> ");
    scanf_s("%d", &maze_size);
    for (int i = 0; i < maze_size; i++) {
        printf("%d행: ", i);
        scanf_s("%s", &maze[i], sizeof(char) * maze_size + 1);
    }
}

void push_loc(stackType* s, int x, int y) {
    if (x < 0 || y < 0) return;
    if (x >= maze_size || y >= maze_size) return;
    if (maze[x][y] != WALL && maze[x][y] != PATH) {
        element tmp;
        tmp.x = x;
        tmp.y = y;
        push(s, tmp);
    }
}

void print_maze() {
    printf("\n");
    for (int i = 0; i < maze_size; i++) {
        printf("%s\n", maze[i]);
    }
}

int neighbor(element next, element back) {
    if ((next.x - 1) == back.x && next.y == back.y) return 1;   // top
    if ((next.x + 1) == back.x && next.y == back.y) return 1;   // bot
    if (next.x == back.x && (next.y - 1) == back.y) return 1;   // left
    if (next.x == back.x && (next.y + 1) == back.y) return 1;   // right
    return 0;
}

int main(void) {
    int x, y, top;
    char buf[10];
    stackType s;
    stackType path;
    element here = { 0, 0 };

    init_stack(&s);
    init_stack(&path);
    init_maze();
    push(&path, here);

    while (maze[here.x][here.y] != GOAL) {
        top = s.top;
        x = here.x;
        y = here.y;
        maze[x][y] = PATH;
        gets_s(buf, 10);
        print_maze();

        //maze[row][col]
        push_loc(&s, x - 1, y);    // top
        push_loc(&s, x + 1, y);    // bot
        push_loc(&s, x, y - 1);    // left
        push_loc(&s, x, y + 1);    // right      

        if (top == s.top) {
            element move = peek(&s);
            while (1) {
                element check = pop(&path);
                if (neighbor(move, check)) {
                    push(&path, check);
                    break;
                }
                maze[check.x][check.y] = VISITED;
                print_maze();
            }
        }
        if (is_empty(&s)) {
            printf("\nFail\n");
            system("pause");
            return 1;
        }
        here = pop(&s);
        push(&path, here);

        /*debuging code
        print_stack(&s);    // 갈 길 스택
        print_stack(&path); // 경로 스택
        */
    }
    printf("\nSuecess\n");
    system("pause");
    return 0;
}


/*
10
0111110000
0001111011
1100011011
1110111000
1110001110
1100100000
1101111111
1100001101
111110010G
1111110001
*/
/*
6
001011
101001
001100
100000
001110
10011G
*/

 

stack.h

#include <stdio.h>
#include <string.h>
#include <stdio.h>

typedef struct {
    int x;
    int y;
}element;

typedef struct {
    element* stack;
    int top;
    int capacity;
} stackType;

void init_stack(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
void push(stackType*, element item);
element pop(stackType* s);
element peek(stackType* s);
void delete_stack(stackType* s);
void print_stack(stackType* s);

 

stack.c

#include "stack.h"

void init_stack(stackType* s) {
    s->top = -1;
    s->capacity = 8;
    s->stack = (element*)malloc(sizeof(element) * s->capacity);
}

int is_full(stackType* s) {
    return (s->top >= (s->capacity - 1));
}

int is_empty(stackType* s) {
    return (s->top <= -1);
}

void push(stackType* s, element item) {
    if (is_full(s)) {
        s->capacity *= 2;
        s->stack = (element*)realloc(s->stack, s->capacity * sizeof(element));
        printf("\n*** Extend Array %d => %d ***\n\n", s->capacity / 2, s->capacity);
    }
    s->stack[++(s->top)] = item;
}

element pop(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[(s->top)--];
}

element peek(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[s->top];
}

void delete_stack(stackType* s) {
    free(s);
}

void print_stack(stackType* s) {
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->stack[i]);
    }
    printf("\n");
}