프로젝트정리 1주차 : 미로를텍스트파일로만들어출력하는프로그램작성. 2주차 : 텍스트형태의미로를 MC의그래픽기능을이용하여그리는프로그램작성. 3주차 : 미로에서길찾는프로그램작성. Dept. of CS, Sogang Univ. 1
DS를이용한미로길찾기문제 DS를이용한미로길찾기문제는 2주차까지설계한미로의출발점과도착점을연결하는가장짧은경로를탐색해출력하는문제이다. NxM 미로의출발점과도착점은각각 1 행1열과 M행N열의방으로설정한다. 실험에서는 [ 도구 ]-[DS] 메뉴를선택하거나 DS 버튼을선택하면아래그림의 (a) 에나타난탐색했던경로와 (b) 에나타난탈출경로를모두표시한다. 두경로는서로구분이가능하도록색을달리해서표시하거나 hatch등을이용하도록하자. Dept. of CS, Sogang Univ. 2
입력 미로텍스트파일 (~.maz) 출력 미로텍스트파일 (~.maz) 을읽어들이면아래그림과같이화면에출발점 ( 초록색 ) 과도착점 ( 빨간색 ) 이표시된미로를출력한다. [ 도구 ]-[DS] 메뉴를선택하거나 DS 버튼을클릭하면 DS 탐색을수행한다. 아래그림과같이출발점과도착점을연결하는탈출경로와경로탐색수행중방문한모든길을서로구분이갈수있도록출력한다. Dept. of CS, Sogang Univ. 3
문제해결방법 미로길찾기문제 (1) : DS 일반적으로알려진 DS 알고리즘은아래 (a) 와같이재귀적형태이다. 재귀함수의경우함수가자기자신을호출할때 parameter 를넘겨주기위해 (b) 와같이컴퓨터내부의 stack memory 를사용한다. 만약매우큰사이즈의미로가입력될경우 DS 과정에서 stack overflow 가발생할가능성이있으므로반복 (iterative) 함수의형태로구현할필요가있다. void dfs (int v) {/* depth first search of a graph beginning at v*/ nodepointer w; visited[v] = TRUE; printf( %5d, v); for (w = graph[v]; w; w = w->link) if(!visited[w->vertex]) dfs(w->vertex); (a) 재귀적형태의 DS(Depth irst Search) Top... dfs parameters dfs() parameters main() (b) Stack memory Dept. of CS, Sogang Univ. 4
+-+-+-+-+ +-+ + + + +-+-+ + + +-+-+-+-+ PRJ-2 미로 (Maze) 3 주차 Recursive DS C D E H I J K L C D E H I J K L DS(v) { mark v as visited; printf( v ); // do somthing for (each unvisited vertex u adjacent to v) { mark edge ( v u ); // crossing edge DS(u); PRINT(visiting order) DS() DS() DS() DS() DS(C) DS(D) DS(K) DS(L) DS(H) DS(E) DS(J) DS(I) system stack (ret addr 제외 ) Dept. of CS, Sogang Univ. 5 H DL CK I EJ C D K L H E J I
Recursive DS with TRET int DS(v) { mark v as visited; if ( v == target ) { printf( v ); return TRET_MEET; for (each unvisited vertex u adjacent to v) { if ( DS(u) == TRET_MEET ) { mark edge ( v u ); printf( v ); return TRET_MEET; return STILL_INDIN; DS() DS() DS() DS() DS(C) DS(D) DS(K) DS(L) C D E H I J K L DL CK system stack (ret addr 제외 ) PRINT (backward) L K Dept. of CS, Sogang Univ. 6
Iterative DS void DS(v) { init a stack S; S.push ( v ); mark v as visited; // may print v while ( S!= empty ) { if ( S.top has an unvisited adjacent node ) { u = an unvisited, adjacent node to S.top; S.push(u); // may print v, and mark (v,u) mark u as visited; else { S.pop ( ); C D E H I J K L DL CK stack PRINT (backward) C D K L Dept. of CS, Sogang Univ. 7
Iterative DS with Target void DS(v) { init a stack S; S.push ( v ); mark v as visited; // may print v while ( S!= empty ) { if ( S.top == target ) return; if ( S.top has an unvisited adjacent node ) { u = an unvisited, adjacent node to S.top; S.push(u); // may print v, and mark (v,u) mark u as visited; else { S.pop ( ); void backtracing( void ) { u = nill; while ( S!= empty ) { S.pop( &v ); if ( u is not nil ) mark v, u, (v - u); u = v; C D E H I J K L stack PRINT (backward) Dept. of CS, Sogang Univ. 8 DL CK C D K L
S ( reath irst Search) fs(v) { Init a queue Q; C D E H I J K L Q.enqueue(v); mark v as visited; while ( Q!= EMPTY) { w = Q.dequeue(); // may print w for ( each unvisited node u adjacent to w ) { mark u as visited // set u.parent = w // later u.parent will be used to find a path Q.enqueue(u); queue KJ C EJ Dept. of CS, Sogang Univ. 9
문제해결방법 아래그림처럼미로는그래프 (node 를 root 로갖는 spanning tree) 로표현가능하다. DS 알고리즘을반복함수형태로구현하기위해더이상방문할수있는자식 node 가존재하지않는 node 에서이전 node 로되돌아가기위하여현재까지거쳐왔던 node 들을저장할 stack 이필요하다. Dept. of CS, Sogang Univ. 10
문제해결방법 node 부터시작하여그래프로변환된미로를 DS 탐색방법으로계속탐색하면서출구인 node Y 를찾을때, 아래그림 (a) 의 처럼방문한적이없었던자식 node 가더이상존재하지않는 vertex 에도달하게되면 (b) 처럼 stack 에저장해둔 node 를 pop 시켜서이전 node 로되돌아갈수있을것이다. 자신이구현한미로의자료구조를어떻게 stack 에저장할것인지생각해보자. (a) (b) Dept. of CS, Sogang Univ. 11
숙제 미로길찾기문제 (2) : S 3 주차실습에서완성한프로그램을바탕으로 S 버튼을누르면 S 방법을통한탈출 경로및탈출과정에서방문했던모든경로를표시하는프로그램을작성한다. 입출력형식은실험시간에해결한완전미로생성문제와동일하다. 입력 : 미로텍스트파일 (~.maz) 출력 : [ 도구 ]-[S] 메뉴를선택하거나 S 버튼을클릭하면 S 탐색을수행한다. 아래그림과같이출발점과도착점을연결하는탈출경로와경로탐색수행중방문한모든길을서로구분이갈수있도록출력한다. Dept. of CS, Sogang Univ. 12
보고서작성 예비보고서 DS 와 S 의시간복잡도를계산하고그과정을설명한다. 자신이구현한자료구조상에서 DS 와 S 방법으로실제경로를어떻게찾는지설명한다. 특히 DS 알고리즘을 iterative 한방법으로구현하기위한방법을생각해보고제시한다. 작성한예비보고서는실험시작전제출하여야한다. 결과보고서 실습및숙제로작성한프로그램의알고리즘과자료구조를요약하여기술한다. 완성한알고리즘의시간및공간복잡도를보이고실험전에생각한방법과어떻게다른지아울러기술한다. 자신이설계한프로그램을실행하여보고 DS, S 알고리즘을서로비교한다. 각각의알고리즘은어떤장단점을가지고있는지, 자신의자료구조에는어떤알고리즘이더적합한지등에대해관찰하고설명한다. 작성한숙제프로그램을공지한제출요령에의거하여기한내제출하시오. 요청이있을경우실험시간에작성한프로그램도아울러제출한다. Dept. of CS, Sogang Univ. 13