스택과 큐를 이용한 미로찾기

최초 등록일
2010.08.08
최종 저작일
2010.08
21페이지/워드파일 MS 워드
가격 2,000원 할인쿠폰받기
판매자boilp**** 54회 판매
다운로드
장바구니

소개글

미로를 찾는 과정을 통해서 스택과 큐를 활용하는 것이 이번 과제이다. 실제 사람이 미로를 찾는다고 생각하면 감에 의해서 길을 찾아갈 것이다. 하지만 신중한 사람이라면 자신이 간 길에 표시를 해두고 또, 갈림길에서 먼저 가야 할 길을 정하는 방식을 택할 것이다.
자신이 간 길을 표시하고 다시 돌아올 수 있도록 하는 것이 바로 스택을 이용한 것이다. 길을 찾아 앞으로 나아가면서 스택에 길의 정보와 방향을 저장한다. 그리고 만약 막다른 골목에 이르게 되면 pop을 통해서 자신의 이전 정보를 꺼내서 다시 돌아간다. 이렇게 돌아가서 다시 자신이 가지 않은 길을 따라 나아간다. 그렇다면 이 사람은 미로가 막혀있지 않다면 충분히 미로를 탈출 할 수 있다.

목차

1. Introduction

2. Method & experiment
Problem 1-1) 지도 그리기, push & pop 함수
Problem 1-2) Stack 이용, 탈출 경로 표시(시계방향)
Problem 1-3) Stack 이용, 탈출 step수 표시(시계방향)
Problem 1-4) Stack 이용, 탈출경로 및 step수 표시(반시계 방향)
Problem 1-5) 시계방향과 반시계 방향 비교, Big-oh 분석
Problem 2-1) Queue 이용 탈출경로 탐색(시계방향)
Problem 2-2) Queue 이용 탈출경로 탐색(반시계 방향)
Problem 2-3) Queue 이용, Big-oh분석

3. Flow Chart

4. Result

5. Source code

6. Reference

본문내용

1. Introduction
미로를 찾는 과정을 통해서 스택과 큐를 활용하는 것이 이번 과제이다. 실제 사람이 미로를 찾는다고 생각하면 감에 의해서 길을 찾아갈 것이다. 하지만 신중한 사람이라면 자신이 간 길에 표시를 해두고 또, 갈림길에서 먼저 가야 할 길을 정하는 방식을 택할 것이다.
자신이 간 길을 표시하고 다시 돌아올 수 있도록 하는 것이 바로 스택을 이용한 것이다. 길을 찾아 앞으로 나아가면서 스택에 길의 정보와 방향을 저장한다. 그리고 만약 막다른 골목에 이르게 되면 pop을 통해서 자신의 이전 정보를 꺼내서 다시 돌아간다. 이렇게 돌아가서 다시 자신이 가지 않은 길을 따라 나아간다. 그렇다면 이 사람은 미로가 막혀있지 않다면 충분히 미로를 탈출 할 수 있다.
큐를 이용한 미로해결은 위의 방식과 조금은 다르다. 자신이 미로의 갈림길에 위치한다면 그 위치에서 갈 수 있는 방향의 길을 한 걸음씩 나가면서 조사해본다. 그리고 다시 앞으로 나가 또 조사하고 하는 방식으로 선택한다. 큐는 FIFO방식이므로 다시 돌아가는 알고리즘을 구현해서 최단 경로를 알아내는 것이 쉽지는 않다. 따라서 큐를 이용한 미로 찾기에서는 step수만 표기하도록 한다.

2. Method & experiment
Problem 1-1) 지도 그리기, push & pop 함수
1번 문항은 미로 문제를 해결하기 위해서 stack을 이용할 것이다. Stack을 이용하는 데는 가장 최상위 위치를 표시하는 top변수와 push, pop함수가 기본적으로 필요하다. top변수는 global변수로 최초 -1로 static선언을 해주었다. 그리고 push와 pop함수는 교재나 강의 노트에 적혀 있는 것과 마찬가지로 아래와 같이 지정해 주었다.

참고 자료

- 알기 쉽게 해설한 C [Herbert Schildt 저, 우진운 유해영 역]
- C로 쓴 자료구조론 [Horowitz 저, 이석호 역]

자료문의

ㆍ이 자료에 대해 궁금한 점을 판매자에게 직접 문의 하실 수 있습니다.
ㆍ상업성 광고글, 욕설, 비방글, 내용 없는 글 등은 운영 방침에 따라 예고 없이 삭제될 수 있습니다.
ㆍ다운로드가 되지 않는 등 서비스 불편사항은 고객센터 1:1 문의하기를 이용해주세요.

판매자 정보

boilp****
회원 소개글이 없습니다.
판매지수
ㆍ판매 자료수
42
ㆍ전체 판매량
973
ㆍ최근 3개월 판매량
5
ㆍ자료후기 점수
평균 A
ㆍ자료문의 응답률
받은문의없음
판매자 정보
ㆍ학교정보
  • 비공개
ㆍ직장정보
  • 비공개
ㆍ자격증
  • 비공개
  • 위 정보 및 게시물 내용의 진실성에 대하여 해피캠퍼스는 보증하지 아니하며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
    위 정보 및 게시물 내용의 불법적 이용, 무단 전재·배포는 금지되어 있습니다.
    저작권침해, 명예훼손 등 분쟁요소 발견시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.

    찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

    더보기
    상세하단 배너
    우수 콘텐츠 서비스 품질인증 획득
    최근 본 자료더보기
    스택과 큐를 이용한 미로찾기 무료자료보기