큐를 통한 미로찾기(최단거리)

큐를 통한 미로찾기(최단거리)

1. 하나의 큐를 만든다.
2. 위치 (0,0)은 이미 방문한 위치임을 표시
3. 큐가 빌 때까지 4를 반복한다.

   4.  1. 큐에서 하나의 위치p를 꺼낸다.
       2. p에서 한 칸 떨어진 위치들 중에서 이동 가능하면서 아직 방문하지 않은 모든 위치들을 방문된 위치임을 표시하고 큐에 넣는다.
       3. 만약 그 위치가 출구라면 종료한다.
      

    Queue queue = create();
    Position cur;
    cur.x=0;
    cur.y=0;

    enqueue(queue,cur);

    maze[0][0]=-1;
    bool found=false;

    while(!is_empty(queue))
    {
        Position cur=dequeue(queue);
        for(int dir=0;dir<4;dir++)
        {
            if(movable(cur,dir))
            {
                Position p=move_to(cur,dir);
                maze[p.x][p.y]=maze[cur.x][cur.y];
                if(p.x==n-1 && p.y==n-1)
                {
                    printf("Found the Path\n");
                    found=true;
                    break;
                }
            }
                
            
        }

    }

Deque ( Double Ended Queue)

양 쪽 끝에서 삽입과 삭제가 허용되는 큐 덱혹은 디큐라고 읽음

우선순위 큐(priority queue)

큐에 들어온 순서와 무관하게 큐에 저장된 값들 중에서는 가장 큰 값이 (혹은 가장 작은값이) 먼저 꺼내지는큐

대표적으로 이진 힙 (binary heap)