[자료구조 - C언어] 자료구조 제17강: 스택의 응용 - 미로 찾기

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 미로 찾기 - 스택

• 2차원 NxN 배열
  • 입구는(0, 0), 출구는 (N-1, N-1)
• 다음을 반복
  • 현재 위치에 방문했다는 표시를 해서 무한 루프를 방지
  • 현재 위치가 출구라면 종료
  • 현재 위치에서 일정한 규칙으로 다음 위치로 이동
    • 북→동→남→서 순서로 이동
    • 아직 안 가본 위치이고 && 벽이 아니고 && 미로의 외부가 아니면 이동
  • 만약 북, 동, 남, 서 어디로도 이동하지 못했다면 현재 위치에 도달하기 직전 위치로 이동한다.
    • 만약 돌아갈 위치가 없다면 원래 길이 없는 미로
    • 어떻게 돌아갈 것?? ⇒ 스택을 사용해서
      • 현재 위치를 스택에 push하고 다음 위치로 이동 → 스택의 top에는 항상 직전 위치가 저장
      • 이동할 수 없다면 → 스택에서 pop해서 이전 위치로 되돌아감
        • 이때 되돌아간 위치도 표시

 

2. 스택으로 미로찾기 구현

2-1. maze.c

//maze.c

#include <stdio.h>
#include "stackADT.h"
#include "pos.h"

#define MAX 100
#define PATH 0         //지나갈 수 있는 위치
#define WALL 1         //지나갈 수 없는 위치
#define VISITED 2      //이미 방문한 위치
#define BACKTRACKED 3  //방문했다가 되돌아 나온 위치

int maze[MAX][MAX];
int n;    //미로의 크기

void read_maze();
void print_maze();
bool movable(Position pos, int dir);

int main(){
    read_maze();    //maze.txt 파일로부터 미로의 모양을 배열 maze로 입력받기

    Stack s = create();    //위치(Position)를 저장할 스택
    Position cur;              //항상 현재 위치를 표현
    cur.x = 0;
    cur.y = 0;
 
    while(1)
    {
        maze[cur.x][cur.y] = VISITED;       //현재 위치를 방문했다고 표시
        if(cur.x == n-1 && cur.y == n-1){   //현재 위치가 출구라면 종료
            printf("Found the path.\\n");
            break;
        }
        
        bool forwarded = false;    //4방향 중 한 곳으로 이동에 성공했는지를 표시 - 되돌아 나가야하는지를 알려줌
        for(int dir = 0 ; dir<4; dir++){    //0:N, 1:E, 2:S, 3:W
            if(movable(cur, dir)==1){       //현재 위치에서 dir 방향으로 이동할 수 있는지 검사
                push(s, cur);               //이동할 수 있다면 현재 위치를 스택에 push
                cur = move_to(cur, dir);    //dir방향으로 한 칸 이동한 새로운 위치를 cur
                forwarded = true;           //이동에 성공
                break;
            }
        }
        if(!forwarded){    //이동에 성공하지 못했다면 ~ 되돌아가야함
            maze[cur.x][cur.y] = BACKTRACKED;    //현재 위치를 되돌아간 위치라 표시
            //현재 위치에 오기 이전 위치가 존재하지 않는다 == 출발점에 서 있다
            //== 출발점에서 아무 방향으로도 새롭게 가볼 수 없다 == 원래 길이 없는 미로, 출구가 없는 미로
            if(is_empty(s)){
                printf("No path exists.\\n");
                break;
            }
            cur = pop(s);    //스택에서 pop한 위치가 새로운 현재 위치(cur)
        }
    }
    print_maze();
}

//txt파일로 부터 maze를 읽는 함수
void read_maze(){
    char filePath[200] = "/Users/파일위치~";
    
    FILE *fp = NULL;
    char buf1[256] = "";
    char *buf2 = NULL;
    
    fp = fp = fopen(filePath, "r");
    if(fp != NULL){
        
        buf2 = fgets(buf1, sizeof(buf1), fp);
        n = atoi(strtok(buf2, " "));

        for (int i = 0; i<n; i++){
            buf2 = fgets(buf1, sizeof(buf1), fp);
            int j = 0;
            maze[i][j++] = atoi(strtok(buf2, " "));
            while(j<n){
                maze[i][j++] = atoi(strtok(NULL, " "));
            }
        }
    }else{
        printf("No such file exists.\\n");
    }
    fclose(fp);
}

//cur에서 dir방향으로 이동할 수 있는지 검사
//0:N, 1:E, 2:S, 3:W
bool movable(Position pos, int dir){
    //maze 내부
    if(pos.x >= 0 &&  pos.x < n && pos.y >= 0 && pos.y < n){
        //maze 내부 -> 외부 이동 금지
        //북동남서 순서로
        if(pos.x == 0 && dir == 0)
            return 0;
        else if(pos.y == n-1 && dir == 1)
            return 0;
        else if (pos.x==n-1 && dir == 2)
            return 0;
        else if(pos.y == 0 && dir == 3)
            return 0;
        
        
        //북: x-1, y
        if(dir == 0 && maze[pos.x - 1][pos.y]==PATH)
            return 1;
        //동: x, y+1
        else if(dir == 1 && maze[pos.x][pos.y + 1]==PATH)
            return 1;
        //남: x+1, y
        else if(dir == 2 && maze[pos.x + 1][pos.y]==PATH)
            return 1;
        //서: x, y-1
        else if(dir == 3 && maze[pos.x][pos.y - 1] == PATH)
            return 1;
    }
    return 0;
    
}

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

2-2. pos.h

//pos.h

#ifndef POS_H
#define POS_H

//x좌표와 y좌표로 이루어진 위치 구조체
typedef struct pos{
    int x, y;
}Position;

Position move_to(Position pos, int dir);

#endif /* POS_H */

2-3. pos.c

//pos.c

#include "pos.h"
 
//북, 동, 남, 서 방향으로 한 칸 이동할 때 x좌료와 y좌표의 변화량
int offset[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

//dir 방향으로 한 칸 이동한 위치를 리턴
Position move_to(Position pos, int dir){
    Position next;
    next.x = pos.x + offset[dir][0];
    next.y = pos.y + offset[dir][1];
    return next;
}

2-4. stackADT.h 수정

• 14강, 15강 코드 바탕으로 수정

//stackADT.h

#include "pos.h"
typedef Position Item;

 

3. 알고리즘의 개선

• 되돌아온 방향을 검사할 필요 없도록
  • BACKTRACKED로 저장하기 때문에 movable함수를 통과할 수 없지만
  • 굳이 확인할 필요도 없다.
• 스택에 좌표대신 방향을 저장하는 것은??
  • 하나의 정수만 저장해도 충분하다.

3-1. stackADT.h 수정

//stackADT.h

typedef int Item;

3-2. maze.c 수정

//maze.c 

...

int init_dir = 0;    //개선) 어떤 위치에 도착했을 때 처음으로 시도해 볼 이동방향, 초기화 값은 북

...

while(1)
    {
        maze[cur.x][cur.y] = VISITED;        //현재 위치를 방문했다고 표시
        if(cur.x == n-1 && cur.y == n-1){    //현재 위치가 출구라면 종료
            printf("Found the path.\\n");
            break;
        }
        
        bool forwarded = false;    //4방향 중 한 곳으로 이동에 성공했는지를 표시 - 되돌아 나가야하는지를 알려줌
        for(int dir = init_dir ; dir<4; dir++){    //0:N, 1:E, 2:S, 3:W
            if(mavable(cur, dir)==1){   //현재 위치에서 dir 방향으로 이동할 수 있는지 검사
				//push(s, cur);         //이동할 수 있다면 현재 위치를 스택에 push
				
                //개선) 스택에는 현재 위치 대신 이동하는 방향을 push
                push(s, dir);    

                cur = move_to(cur, dir);    //dir방향으로 한 칸 이동한 새로운 위치를 cur
                forwarded = true;           //이동에 성공
								
				//개선) 처음 방문하는 위치에서는 항상 0 방향부터 시작
                init_dir = 0; 

                break;
            }
        }
        if(!forwarded){    //이동에 성공하지 못했다면 ~ 되돌아가야함
            maze[cur.x][cur.y] = BACKTRACKED;    //현재 위치를 되돌아간 위치라 표시
            //현재 위치에 오기 이전 위치가 존재하지 않는다 == 출발점에 서 있다
            //== 출발점에서 아무 방향으로도 새롭게 가볼 수 없다 == 원래 길이 없는 미로, 출구가 없는 미로
            if(is_empty(s)){
                printf("No path exists.\\n");
                break;
            }

			//cur = pop(s);    //스택에서 pop한 위치가 새로운 현재 위치(cur)

			//개선) 이전 위치를 pop
            int d = pop(s);    
            cur = move_to(cur, (d+2) % 4);    //개선) 이전 위치와 반대방향으로 이동
            init_dir = d+1;    //개선) 되돌아간 위치에서는 d+1번 방향부터 시도
        }
    }
    print_maze();
}

 

4. 결과

4-1. maze.txt

8 8
0 0 1 1 0 1 0 1
1 0 1 1 0 1 1 1
1 0 0 1 0 1 1 1
1 0 1 1 0 1 1 1
1 0 0 0 0 1 1 1
1 1 0 0 0 1 1 1
1 1 0 0 0 1 1 1
1 1 0 1 0 0 0 0

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/5Q3L_kNCzw0