[자료구조 - C언어] 자료구조 제18강: 큐의 개념과 응용 - 미로찾기

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

 

1. 미로 찾기

• DFS(Depth First Search: 깊이 우선 탐색) - recursion, stack
  • 더 이상 갈 곳이 없을 때까지 갔다가 다시 되돌아 나와서 진행
• BFS(Breath First Search: 너비 우선 탐색) - queue
  • 출발점에서 한 칸 떨어진 지점을 탐색
  • 출발점에서 두 칸 떨어진 지점을 탐색
  • … 출발점에서 n 칸 떨어진 지점을 탐색 ~ 동심원 형태로

1-1. 너비 우선 탐색으로 미로 찾기

(1) 하나의 큐를 만든다.

(2) 위치(0, 0)는 이미 방문한 위치임을 표시하고, 큐에 위치 (0,0)을 넣는다.

     (3) 큐가 빌 때까지 반복

         (4) 큐에서 하나의 위치 p를 꺼낸다.

         (5) p에서 한 칸 떨어진 위치들 중
               이동 가능(북→동→남→서 방향) && 아직 방문하지 않은 모든 위치들을

               방문된 위치임을 표시하고 큐에 넣는다. (이때 큐에 넣는 순서는 중요하지 않음)

         (6) 만약 그 위치가 출구라면 종료

• BFS를 이용해서 미로 찾기를 하면 최단 경로를 찾을 수 있다.
  • 출구에서 감소하는 방향으로 따라가면 입구에 도달한다.
  • DFS는 최단 경로를 찾지는 않는다.
• 큐는 FIFO이기 때문에
  • L1을 찾아 큐에 넣고 → 큐에서 L1을 꺼내 → 꺼낸 위치에서 순차적으로 L2를 찾는 것을 반복하면서 레벨을 늘려 나간다.
• DFS, BFS 참고 

 

2. 큐로 미로 찾기 구현

2-1. maze.c

//  maze.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queueuADT.h"
#include "pos.h"

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

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

int main(){
    read_maze();
    
    Queue q = create();
    Position cur;    //현재 위치
    cur.x = 0;
    cur.y = 0;
    
    enqueue(q, cur);    //출발점을 큐에 넣고 시작
    
    //벽과 구분하기 위해서, 추가 배열을 쓰지 않기 위해
    //방문했다는 표시를 음수로, 시작은 -1
    //한 칸 더 전진하면 -1을 더한다
    //경로를 찾을 때 출구에서 숫자가 1 증가하는 방향으로 따라가면 입구에 도달
    maze[0][0] = -1;
    //bool found = false;
    
    //출구에 도달할 때 까지 = 큐가 빌 때 까지
    //출구가 없는 미로라도 큐가 비면 종료
    while(!is_empty(q)){
        Position cur = dequeue(q);    
        //cur에 인접한 4개의 방향으로 이동할 수 있는지 검사
        for(int dir = 0; dir<4; dir++){
            if(movable(cur, dir)){
                //이동한 방향을 p
                Position p = move_to(cur, dir);
                //이동한 칸의 값 = 현재 위치 값 -1
                maze[p.x][p.y] = maze[cur.x][cur.y] -1;
                //p가 출구
                if(p.x == n-1 && p.y == n-1){
                    printf("Found the path.\\n");
                    //found = true;
                    break;
                }
                //이동한 위치가 출구가 아니라면 큐에 삽입
                enqueue(q, p);
            }
        }
    }
    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("%4d ", 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. 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

2-5. 결과

 

3. 큐의 변형

• 사용하는 용도가 스택보다 다양하다.
• Deque(Double Ended Queue)
  • 양 쪽 끝에서 삽입과 삭제가 허용되는 큐
  • ‘덱’ 또는 ‘디큐’라고 읽음
• 우선순위 큐(Priority Queue)
  • 큐에 들어온 순서와 무관하게 큐에 저장된 값들 중에서
    • 가장 큰 값이: 최대 우선순위 큐(Maximum P. Q)
    • 가장 작은 값이: 최소 우선순위 큐(Minimum P. Q)
    • 부호만 바꾸기 때문에 사실상 같은 구조
  • 가장 먼저 꺼내지는 큐
  • 대표적인 구현 방법으로는 이진 힙(binary heap)이 있음
    • 우선순위 큐는 데이터의 삭제와 삽입이 순서와 관련 없기 때문에 배열이나 연결 리스트 같은 1차원적인 자료구조로는 성능에 한계가 있다.

 

 

 

 

---

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

https://youtu.be/16SLOYDCYuc