2007. 09. 17 Prof. Kyungshik Lim Kyungpook National University 자료구조 과제 1 (maze program) 2007. 09. 17 Prof. Kyungshik Lim Kyungpook National University

목 차 Maze program 과제 설명 Appendix 1. 미로파일 샘플 Appendix 2. 파일 입력을 통한 미로 저장 목 차 Maze program 과제 설명 Appendix 1. 미로파일 샘플 Appendix 2. 파일 입력을 통한 미로 저장 Appendix 3. 파일입출력 프로그램 실행방법

Maze program 과제 설명(1/3) Maze problem 정의 Maze problem의 특징 1 주어진 미로의 경로를 통하여 좌측 상단에서 우측 하단까지 이동하여 미로를 탈출하는 문제 Maze problem의 특징 미로는 숫자 0, 1으로 구성 0 : 경로, 1 : 벽 미로의 좌측 상단에서부터 시작, 우측하단으로 빠져나옴 문제해결을 위해 미로를 벽(1)으로 막음 ex) 1

Maze program 과제 설명(2/3) 동작과정 좌표 (1, 1)에서 출발하여 미로 파일의 우측 하단 탈출구까지 이동 경로 탐색 순서 북  북동  동  남동  남  남서  서  북서 경로 탐색, 이동 이동 경로가 있을 때는 스택에 저장 후 이동 사방이 막혀있는 경우 이전 경로로 이동하고, 스택의 저장된 정보 꺼냄 미로에서 탈출 할 때까지 경로의 탐색과 이동 반복 Ex) 탐색 Ex) 이동 막힌 경우 되돌아 옴 (스택에서 해당 데이터 Pop) 1 1 1 8 2 7 3 6 5 4

Maze program 과제 설명(3/3) 요구사항 과제 제출 프로그램 작성언어 : C, C++ txt파일 입출력을 통해 미로의 구조를 배열에 저장 자세한 내용은 [Appendix 1, 2] 참고 프로그램 종료시 미로 탈출 경로 출력 ex) 1,1(E) -> 1,2(S) -> ... -> n,m(E) -> Goal 과제 제출 고현욱 : hwko@ccmc.knu.ac.kr 메일제목 : [자료구조] 과제1_200x037xxx_홍길동 첨부파일 파일명 : 과제1_200x037xxx_홍길동.zip 내 용 : 소스파일(.c), 실행파일(.exe), 문서파일(.hwp or .doc) 제출일자 2007년 9월 27일(목) 까지 기타 궁금한 사항은 http://wicom.knu.ac.kr의 Q&A 혹은 해당 조교에게 메일로 문의하십시오.

Appendix 1. 미로파일 샘플 미로파일 샘플(data.txt) 가로, 세로 크기 : 10ｘ10 (최대 30ｘ30까지 허용가능) 미로 파일은 숫자 0, 1로 구성 가로의 숫자와 숫자 사이는 space bar(␣)’로, 세로의 숫자와 숫자 사이는 ‘Enter(↲)’로 구분 파일의 마지막은 ‘Enter(↲)’ 미포함 0␣1␣0␣1↲ 0␣0␣0␣1↲ 1␣0␣0␣0

Appendix 2. 파일 입력을 통한 미로 저장(1/2) 샘플 파일 입출력 소스코드(sample.c) #define HEIGHT 32 // maze 배열의 세로 개수 #define WIDTH 32 // maze 배열의 가로 개수 int main() { int now_Width=1, now_Height=1; // 파일 저장 좌표 int maze[WIDTH][HEIGHT]; // maze 배열 선언 FILE *fp; // 파일 포인터 선언 scanf("%s", filename); // 파일 이름 입력 if((fp = fopen(filename, "r")) == NULL) { // 파일 열기, 파일포인터를 fp에 저장 while(!feof(fp)) { // 파일 포인터를 파일의 종료 부분까지 증가

Appendix 2. 파일 입력을 통한 미로 저장(2/2) 샘플 파일 입출력 소스코드(sample.c) switch(fgetc(fp)) { // 저장된 데이터(0,1,space bar enter) 구분 case '0' : { // 데이터가 ‘0’인 경우 maze 배열에 저장 maze[now_Width][now_Height]=0; now_Width++; // 가로 좌표 값 증가 break; } case '1' : { // 데이터가 ‘1’인 경우 maze 배열에 저장 maze[now_Width][now_Height]=1; now_Width++; // 가로 좌표 값 증가 break;} case ' ': { // space bar로 입력된 부분 무시 case '\n': { // enter 입력시 배열의 행 변환 now_Width=1; // 가로 좌표 값 초기화 now_Height++; // 세로 좌표 값 증가 break; } }

샘플 파일 저장 Appendix 3. 파일입출력 프로그램 실행방법 생성된 프로젝트 폴더에 샘플파일(data.txt) 복사 샘플파일은 프로젝트 폴더에 복사하여 사용 가능

샘플 파일 입출력 소스코드 실행화면 Appendix 3. 파일입출력 프로그램 실행방법 파일 이름 미로파일 샘플 출력 “data.txt” 입력 미로파일 샘플 출력 10ⅹ10의 내용 출력 출력위치는 1ⅹ1 미로파일 샘플 이외 지역은 1로 채움 Exit 좌표 출력