Week 6 : Maze(with stack) / Circular Queue

< 180515 > 

- 스택의 응용 : 미로탐색

<미로탈출 초기상태>

- 시작좌표는 (1, 0)

- 도착좌표는 (4, 5)

 

- 알고리즘

1) 시작좌표를 현재좌표로 설정

2) 현재좌표가 도착좌표가 아니면

2-1) 현재좌표를 방문체크.

2-2) 현재좌표 기준 상하좌우의 좌표를 스택에 넣음.

2-2-1) 스택에 넣기전, 미로의 영역을 벗어나거나, 이미 방문한 좌표는 스택에 넣지 않는다. (예외처리)

2-3) 스택이 비어 있는지 확인. 비어있다면, 탈출 불가능한 미로

2-4) 스택에서 좌표 하나를 꺼내어 현재 좌표로 변경 후 2)로 돌아간다.

3) 탈출성공.

- 현재좌표 기준 상하좌우 좌표

- 미로 탈출 과정 (현재 위치 : H, 방문체크 : -, 방문체크한 곳 기준 상하좌우의 좌표를 스택에 담음.)

>> 이러한 과정으로 진행이 된다.

- Queue 정의 : 먼저 들어온 데이터가 먼저 꺼내지는 자료구조

- 예시 : 버스에서 줄서기(앞에 선 사람이 먼저 탐), 

            스타크래프트 게이트웨이(질럿, 드라군, 다크 순으로 찍으면 질럿, 드라군, 다크 순으로 나온다.)

- 기본 큐 

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int q[MAX];
    int f, r;
} Queue;
 
void init(Queue * q) {
    q->f = q->r = 0;
}
 
int isEmpty(Queue * q) {
    return (q->f == q->r);
}
 
void enqueue(Queue * q, int data) {
    q->q[(q->r)++] = data;
}
 
int peek(Queue * q) {
    return q->q[q->f];
}
 
int dequeue(Queue * q) {
    return q->q[q->f++];
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
 
    return 0;
}
 

>> 데이터의 삽입은 rear 가, 데이터의 삭제(꺼내기)는 front 를 이용한다.

>> 위와 같이 코드를 작성하면, 배열 앞 공간에 낭비가 발생한다. >> 원형 큐로 대체..!!

- 원형 큐

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct queue {
    int q[MAX];
    int f, r;
} Queue;
 
void init(Queue * q) {
    q->f = q->r = 0;
}
 
int isEmpty(Queue * q) {
    return (q->f == q->r);
}
 
void enqueue(Queue * q, int data) {
    q->r = (q->r+1)%MAX;
    q->q[(q->r)] = data;
}
 
int peek(Queue * q) {
    return q->q[(q->f+1)%MAX];
}
 
int dequeue(Queue * q) {
    q->f = (q->f+1)%MAX;
    return q->q[q->f];
}
 
int main()
{
    Queue q;
    init(&q);
 
    enqueue(&q, 1);
    enqueue(&q, 9);
    enqueue(&q, 9);
    enqueue(&q, 8);
 
    if(!isEmpty(&q)) printf("%d\n", dequeue(&q));
    if(!isEmpty(&q)) printf("%d\n", peek(&q));
 
    return 0;
}
 

>> 처음 비어있는 상태는 f와 r이 같은 곳을 가리킬때..!!

>> 원형큐는 한칸을 비워둔다. 그렇지 않으면 비어있는 상태와 가득차있는 상태를 구분할 수 없게 된다.

>> f가 가리키는 곳는 마지막으로 데이터를 꺼낸 곳이라고 생각하면 된다. 즉 비어있는 곳.

>> 마찬가지로 데이터의 삽입은 r 로, 데이터를 꺼내는 작업은 f 를 이용한다.

>> 원형큐이기 때문에 배열의 마지막 인덱스 다음에 0번째 인덱스로 와야 한다. 

     이를 해결해주는 방법이 배열의 다음 인덱스를 항상 배열의 크기로 나눈 나머지로 처리하면 된다. 

     모듈러 연산을 하면, 배열이 크기보다 작은 인덱스들은 자기 자신이 되지만, 

     마지막인덱스에서 다음으로 넘어가면 배열의 크기가 되는데, 이는 크기로 나눈 나머지를 계산하면 0이 된다.

- 원형큐에서의 문제.

1) 배열의 크기가 8이고, f가 3을, r이 5을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 2개

2) 배열의 크기가 8이고, f가 5을, r이 3을 가리킬 때, 삽입되어 있는 데이터의 갯수는?? 6개