CSED101. Programming & Problem solving Spring, 2014 Programming Assignment #4 (70 points) 마정현 (doitnow0415@postech.ac.kr) Due: 2014.06.01 23:59 Development Environment: Windows Visual Studio 2010 제출물 C Code files (*.c) stack.h, stack.c, assn4_1.c, assn4_2.c 프로그램의소스코드를이해하기쉽도록반드시주석을붙일것. 보고서파일 (.doc(x) or.hwp) 예 ) assn4.doc(x) 또는 assn4.hwp AssnReadMe.pdf 를참조하여작성할것. 소스코드와보고서파일을 LMS를이용하여제출한다. 주의사항 문제의요구사항을반드시지킬것. 모든문제의출력형식은아래의예시들과동일해야하며, 같지않을시는감점이된다. 각문제에제시되어있는파일이름으로제출할것. 그외의다른이름으로제출하면감점또는 0점처리된다. 과제를작성하는데있어서전역변수를선언하여사용할수없다. 이번과제에서는추가기능구현에대한추가점수는없다 컴파일 & 실행이안되면무조건 0점처리된다. 하루 late시 20% 가감점되며, 3일이상지나면받지않는다. (0점처리 ) 부정행위에관한규정은 POSTECH 전자컴퓨터공학부학부위원회의 POSTECH 전자컴퓨터공학부부정행위정의 를따른다. (LMS의과목공지사항의제목 [document about cheating] 의첨부파일인 disciplinary.pdf를참조할것.) Linked list로구현하지않는다. 재귀 (recursion) 함수를사용할수없다.
Problem 1: 스택자료구조구현 (20 점 ) ( 목적 ) 이문제에서는프로그래밍시사용되는자료구조중하나인스택을직접구현해봄으로써, 구조체와포인터를익힌다. ( 스택의정의 ) 스택은쌓아올린더미를의미하며한쪽끝에서만삽입과삭제과일어나는자료구조이다. 즉, 스택구조는아이템을 Last In First Out (LIFO) 방식으로저장하는구조로써, 가장마지막에들어온아이템 ( 아래그림상가장위쪽에위치한 ) 이가장먼저나갈수있도록정의한구조를의미한다. 스택동작그림 (1) (2) (3) (4) (5) (6) (7) - 그림은 (1) 의빈스택에아이템을삽입 (Push) 하고삭제 (Pop) 함에따라스택의변화과정을보여주는그림이다. - 삽입과삭제는현재저장된최상위항목이위치한꼭대기 (top) 에서만일어난다. 그림에서 top은항상가장마지막아이템을가리킨다. - Stack 을배열로구현하면배열인덱스는 0에서시작하므로 top의초기값은 -1 로설정한다. ( 문제 ) 아래 stack.h 파일을이용하여실행예제와같이동작하는스택을구현한다. ( 설명 ) 다운로드받은 assn4.zip의압축을풀면 stack.h 와 stack.c 가주어진다. 스택의선언 (stack.h) 아래에서 Position type은 2차원배열의좌표 (row, col) 값을저장하기위한자료형이다. Stack 에 Push 또는 Pop 되는아이템은구조체 Position type 으로위치좌표 (row, col) 값을저장한다. 그리고, 그아래스택구현을위한함수들이선언되어있다. #ifndef STACK_H #define STACK_H typedef struct { int row; int col; } Position; // stack 에추가또는삭제할아이템의자료형 Position을선언
typedef struct { int top; // stack의마지막아이템의위치저장 int size; // stack의최대사이즈를저장 Position *items_list; // stack 의 Position 타입의정보들을저장할공간을가리키는포인터 } Stack; void initstack(stack *s, int stack_size); int isempty(stack *s); int isfull(stack *s); void push(stack *s, Position item); Position pop(stack *s); Position top(stack *s); void freestack(stack *s); #endif 아래의설명을참고하여제공되는 stack.c 파일에있는함수들을완성시키고, assn4_1.c 에는 main 함수를포함하여아래의실행예제가실행되도록작성한다. 스택오퍼레이션의정의 push: 아이템을스택에추가 pop: 스택의가장마지막에들어온아이템을제거하고반환 top: 스택의가장마지막에들어온아이템을반환 isempty: 스택이비었는지확인 isfull: 스택이가득차있는지확인 아래의실행예제를참고하여스택을구현하자. - 필요하면 string.h 에정의되어있는함수를사용할수있다. (1) 명령어 create: 스택을생성하고초기화한다. 스택은메모리를동적할당받아서사용하도록한다. 모든명령어는 create 명령어수행후에이루어진다고가정한다. create 명령어를입력하면, 스택의크기 (stack_size) 를입력받아스택을초기화한다. Stack *stack; stack = (Stack *) malloc (sizeof(stack) ); initstack(stack); // 초기화하기위해함수호출 void initstack(stack *s, int stack_size); 스택을초기화하는함수로 top 을 -1, size를 stack_size, item_llist = (Position *)calloc(stack_size, sizeof(position) ); 로설정한다.
exit: 동적할당받은메모리를모두 free 시키고프로그램을종료한다. 함수 freestack 을작성해서사용하자. void freestack(stack *s); 스택생성시동적할당받은메모리를 free 시킨다. free를수행해야할동적할당받은메모리목록 - 스택의 item_list - 스택 push: 아이템을스택에추가하는명령어로그림 (1) 의빈스택에서 Push A 를수행하면 스택에 A 가삽입되어그림 (2) 의상태가된다. void push(stack *s, Position item); pop: 스택의가장마지막에들어온아이템을스택에서제거하고그값을반환하는 명령어로그림 (4) 의상태에서 Pop 을수행하면그림 (5) 의상태가된다. Position pop(stack *s); top: 스택의가장마지막에들어온아이템을반환하는명령어로그림 (7) 의상태에서 top 을수행하면아이템 D 를읽어온다. top 수행후, 스택상태의변화는없다. Position top(stack *s); isempty: 스택이비었는지확인하는명령어로비어있으면 1, 그렇지않으면 0 을 반환한다. int isempty(stack *s); isfull: 스택에아이템이가득차있는지확인하는명령어로가득차있으면 1, 그렇지 않으면 0 을반환한다. int isfull(stack *s) (2) 그외함수 void showstack(stack *s); 스택에아이템을삽입한순서대로출력한다. 아래실행예제중 [stack]: (1, 0) (1, 1) (2, 2) 과같이현재스택에존재하는아이템을출력하기위해사용한다 (3) 스택오버플로우 (Overflow) 와언더플로우 (Underflow) - 배열로구현하는스택사이즈는제한이있으므로스택이가득차있을때, push 하고자하면, overflow가발생한다. - 스택이비어있을때, pop과 top 을하고자하면, underflow가발생한다.
실행예제 ) 빨간색글씨는사용자입력이다. 모든명령어는 create 명령어수행후에이루어진다고가정하며틀린입력은없다고가정한다. 예제1) 예제2) create create Input stack size: 3 Input stack size: 2 [stack]: [stack]: push 1 0 isempty [stack]: (1, 0) 1 push 1 1 [stack]: [stack]: (1, 0) (1, 1) push 1 0 push 2 2 [stack]: (1, 0) [stack]: (1, 0) (1, 1) (2, 2) isempty push 3 3 0 Stack Overflow [stack]: (1, 0) [stack]: (1, 0) (1, 1) (2, 2) isfull pop 0 item: (2, 2) [stack]: (1, 0) [stack]: (1, 0) (1, 1) push 3 3 top [stack]: (1, 0) (3, 3) item: (1, 1) isfull [stack]: (1, 0) (1, 1) 1 pop [stack]: (1, 0) (3, 3) item: (1, 1) pop [stack]: (1, 0) item: (3, 3) pop [stack]: (1, 0) item: (1, 0) exit [stack]: 계속하려면아무키나누르십시오 pop Stack Underflow [stack]: exit 계속하려면아무키나누르십시오 ( 주의사항 ) 제출해야파일은 stack.h, stack.c, assn4_1.c 이다. 보고서는 assn4.doc or assn4.hwp 로저장한다. ( 보고서는통합하여작성 ) 화면출력은반드시실행예와같아야한다.
Problem 2: 스택자료구조를이용한미로찾기 (50 점 ) ( 문제 ) Problem1 에서구현한스택을이용하여미로찾기를구현하자. 반드시스택을이용하여 구현한다. ( 재귀함수로구현하지말것 ) ( 문제정의 ) Problem1에서작성한 stack.c와 stack.h를 include 하여사용한다. 파일로부터입력받은미로에서스택자료구조를이용하여길을찾는다. 미로는 N x M 행렬로구성된다. 시작점의좌표는 (1, 0) 이며, 출구의좌표는 (N-2, M-1) 으로고정된다. 한지점에서움직일수있는방향은동, 서, 남, 북네방향이다. ( 문제의개요 ) 다음의 N x M 행렬은주어진미로를나타낸다. # 는벽을의미하며공란 (Blank) 은통로를 의미한다. O 는시작점의위치를나타낸다. 시작점의좌표는 (1, 0) 으로고정되고, G 는출구를 나타내며, 좌표는 (N-2, M-1) 으로고정된다. 시작점으로부터출구까지의 Path 가존재하지 않을수도있다. 출구까지의 Path 가존재하지않을때는출구를찾을수없다는문구를 출력해준다. 가정 : 입, 출구에해당하는좌표에벽 # 은존재하지않는다. 즉, 미로맵을만들때이를 고려할필요가없다. ########################### O # ##### ### # ## ### # ### ##### ### # ## ### # ###### # # # ##### ## ######## ## # # ## ## ## ## # # #### ######### ####### # G ########################### 미로는파일에정해진양식을따른다. 오른쪽그림은위의 8 x 27 미로행렬에대한파일의예이다. 오른쪽그림에서처럼통로는 blank로벽은 # 으로표현된다. 입구와출구의위치가정해져있기때문에, 입구와출구는파일에따로표현하지않는다. (maze1.dat 파일참고 ) 미로파일의첫행에는행 (N) 과열 (M) 이반드시명시되어있으며, 파일로부터이정보를읽어 N x M 크기의배열형태를가지도록동적할당을하여미로를메모리에저장한다. ( 아래의문제힌트부분참고 ) 8 27 ########################### # ##### ### # ## ### # ### ##### ### # ## ### # ###### # # # ##### ## ######## ## # # ## ## ## ## # # #### ######### ####### # ########################### 가정 1: 미로파일이위의정해진양식을벗어나는경우는없다. 가정 2: 미로맵에대한파일첫행의행과열정보가틀린경우는없다.
현재위치에서가능한진행방향을조사할때, 동-> 서-> 남-> 북순서대로조사하여벽이아니고이미방문한곳이아니라면그쪽으로진행하도록한다. 방향을조사하는순서는위의순서를반드시지켜야한다. ( 대각선방향으로이동하는경우는없다 ) 다음진행방향으로의이동에대한연산및미로맵에서현재위치의출력은 0.1초간격으로진행한다. (Sleep함수이용, windows.h에정의 ). 사용방법 : Sleep(100); // Sleep함수에들어가는인자는밀리초를나타냄. 현재위치에서다음위치로진행하는경우, 현재위치에서진행가능한방향중하나를스택에저장하게된다. 이때, 아래의구조체를사용하도록한다. (Problem 1에서사용함 ) Stack 에 push 또는 pop 되는 item type은구조체 Position type 으로위치좌표 (row, col) 를나타낸다. 구조체 Stack type 은 top 과 size( 스택의최대크기 : M*N) 를멤버로가지고있다. typedef struct { int row; int col; } Position; // stack 에추가또는삭제할아이템의자료형 Position을선언 typedef struct { int top; // stack의마지막아이템의위치저장 int size; // stack의최대사이즈를저장 Position *items_list; // stack 의 Position 타입의정보들을저장할공간을가리키는포인터 } Stack; Position을 Stack 에저장하게되는경우는현재위치에서이동가능한지점 ( 동서남북중하나 ) 이벽이아니고아직방문을하지않은경우이다. Stack에는현재까지방문한 Position 들중에서되돌아나오지않은것들이저장된다. 즉, 현재까지알아낸입구에서출구까지의길이저장된다. Stack 에서 Position 를꺼내게되는경우는현재위치를기준으로조사한네방향모두가벽혹은이미방문한곳에해당되는경우이다. 아래의문제힌트의알고리즘을참고하라. ( 문제힌트 ) 스택을이용한미로찾기알고리즘 알고리즘 1. 스택을초기화한다. 2. 출발지점을스택에 push한다. 3. 아래 Description을따라미로를이동한다. 3-1. 이동가능한지점중한곳을 stack에 push 하고이동한다. 이동가능한지점은동-> 서-> 남-> 북순서로조사한다. 3-2. 벽혹은이미지나온점으로사방이둘러쌓여있다면 stack pop을수행하여이전위치로이동한다. 4. 도착점을찾을때까지 3을반복한다.
모식도 미로생성을위한 2차원배열동적할당방법미로맵파일은 character로되어있다. 미로맵은 2차원 char 배열로구현하도록한다. 현재위치 (i, j) 가벽이면 a[i][j] 는 #, 방문하지않은길이면 a[i][j] 는, 방문한위치라면적당한문자를할당하면된다. 미로맵을위한 2차원 char 배열생성은아래를참조한다. char **maze 는 2 차원배열을동적할당받기위한포인터변수이다. 위의예에서, maze_row 와 maze_col 에는파일로부터읽은값인 N 값과 M 값이할당된다고 생각하자.
위의 2 차원배열동적할당에대한모식도 구현을위해 Problem1 에서구현한함수와아래와같은함수를사용하게된다. 반드시아래의함수를구현해야하는것은아니다. char ** readmaze(char *file_name, int *, int *); 파일로부터미로의모양을읽어들여 char ** 타입의행렬을반환한다. fopen(), fclose() 모두이함수안에서이루어지도록한다. void printmaze(char**maze, int, int); 미로맵을출력한다. Stack *findpath(char **maze, int, int); 주어진미로맵에서시작점부터출구까지의길을 Stack에담아돌려준다. void printpath(char **maze, int, int, Stack *); 미로의길을좌표로출력하는데, 반드시시작점에서부터출구로표현되어야한다. void freemaze(char **maze, int); 미로맵을생성하기위해동적할당된메모리를 free 시킨다.
( 실행예 ) (1) 길이있는경우 maze0.dat 프로그램을실행하면아래와같이미로맵을생성하기위해읽어야할파일명을요구한다. 입력받는파일명에는공백이없다고가정한다. 존재하지않는파일명 wrong.dat 를입력한경우에는아래와같은에러메시지를출력후, 프로그램을종료한다. 존재하는파일의파일명 maze0.dat 를아래와같이입력후엔터키를누르면, 입력파일을읽어서 미로맵의초기상태를출력한다. 0. 초기상태 초기상태에서엔터를입력하면길찾기가진행된다. 미로맵에서위치를이동할때마다화면을 아래와같이갱신해준다. 화면을갱신하기전에 system( cls ) 를이용하여화면을지운후미로 맵에서현재까지알아낸입구에서출구까지의길을찾은경로를출력한다.
아래에서 O 는경로이며. 은방문은했지만경로는아니며, 공백은방문을하지않은경우이다. 1. 2. 3. 4. 5. 6. 7. 8.
9. 10. 중간과정생략 출구를찾은경우, 아래와같이시작점부터출구까지좌표로출력하고프로그램은종료된다. 경로출력형식은 printf("[%2d, %2d]", row, col); 문을사용한다. (2) 길이있는경우 maze1.dat - 초기화면 - 마지막결과화면
(3) 길이있는경우 maze2.dat - 초기화면 - 마지막결과화면 (4) 길이없는경우 maze3.dat - 초기화면 - 마지막결과화면 : 시작점부터출구까지의경로를찾지못했을경우엔아래와같이출력한다.
(5) 길이있는경우 maze4.dat - 초기화면 - 마지막출력화면 ( 주의사항 ) 파일이름은 assn4_2.c 로저장한다. 보고서는 assn4.doc or assn4.hwp 로저장한다. ( 보고서는통합하여작성 ) 화면출력은반드시실행예와같아야한다. 프로그램은최소한첨부된 sample data (maze1.dat, maze2.dat, maze3.dat, maze4.dat) 에대해서올바른결과를출력해야한다. 그결과를파일에포함시킬것. 동적할당받은메모리는프로그램종료시 free 시키도록한다.