#21 [C 자료구조] 스택으로 미로 문제 풀기

오늘은 스택으로 풀 수 있는 문제 버전 2를 준비했다. 미로 되시겠다.

머리를 부여잡고 다시 한 번 스택으로 코딩을 시작해보자ㅎ

아이고 두야!

미로(Maze) 문제

미로를 배열 혹은 수열, 아니 애초에 코딩으로 구현할 수 있을까? 당연히 되기 때문에 제목으로 적었을 것이다 ㅎㅅㅎ

지나갈 수 있는 뚫린 길은 0, 벽은 1으로 표시한다.

자 그래프는 일단 그려봤다. 그렇다면 어떻게 스택을 구현하는 것일까?

 

위와 같이 경우의 수를 모두 스택에 쌓음으로써 가능하다. 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 Pop을 이용해 이전 단계까지 돌아온다.

 

미로 문제의 몇 가지 특성은 기억해줘야한다.

1) a*b 미로는 (a+2) * (b+2) 배열이 필요하다.

2) 입구는 [1][1], 출구는 [a][b]

3) 원칙상 오픈된 곳에서는 미로가 8방향으로 움직일 수 있다.

 

미로가 움직일 수 있는 방향을 row와 col로 표현하면 다음과 같다.

미로 알고리즘 짜기

- 경로 탐색

1) 미로 탐색 단계마다 방문 위치와 이동 방향 정보를 스택에 push함

2) 탐색 중 막다른 길에 만날 때마다 이전 위치로 돌아오기 위해 스택에서 pop함

3) 한번 시도한 경로의 재시도 방지를 위해 방문한 경우 mark[raw][col] = 1  으로 바꿔 놓는다.

4) 최대 스택 크기는 미로 내 0의 수 만큼이면 된다.(최대 1번씩 방문)

 

미로 코드 짜기

지금 까지 배워온 정보로 이제 미로 코드를 짜보자.

1) 현재 위치 x에서의 이동 방향에 대한 정의

typedef struct {
    int vert; // 수직 좌표
    int horiz; // 수평 좌표
} offsets;
offsets move[8]; // 이동 가능 방향들의 배열

2) 미로 정보 정의

#define MAX_STACK_SIZE 100 // 최대 100, 0의 수가 최대 100인 경우
typedef struct {
    short int row;
    short int col;
    short int dir;
} element;
element stack[MAX_STACK_SIZE];

3) 미로 서칭 알고리즘 유사 코딩

while (stack is not empty) { /* move to position at top of stack */
    <row, col, dir> = delete from top of stack;
    while (there are more moves from current position) { // 이동할방향이있다면반복
        <next_row, next_col > = coordinates of next move;
        dir = direction of move;
        if ( (next_row == EXIT_ROW) && (next_col == EXIT_COL) )
        		success;
        if ( maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0 ) {
            /* 길이 있고 방문하지 않았다면 */
            mark[next_row][next_col] = 1; // 방문 표시
            add <row, col, dir> to the top of the stack; // 스택에 추가
            row = next_row;
            col = next_col;
            dir = north;
        }
    }
}
printf("No path found\n");

 

4) 미로 서칭 알고리즘 코딩

void path (void){ // 경로가 있다면 패스 출력
    int i, row, col, next_row, next_col, dir;
    int found = FALSE; // 1이면 출구
    element position;
    mark[1][1] = 1; // 방문 설정(시작점)
    top = 0; // 시작점 스택에 push
    stack[0].row = 1;
    stack[0].col = 1;
    stack[0].dir = 1;
    while ( top > -1 && !found ) { // 방문 안한 곳
        position = delete(&top);
        row = position.row;
        col = position.col;
        dir = position.dir;
        while ( dir < 8 && !found ) {
        	next_row = row + move[dir].vert;
			next_col = col + move[dir].horiz;
            if ( next_row==EXIT_ROW
                && next_col==EXIT_COL )
                found = TRUE; // 경로 찾음
            else if ( !maze[next_row][next_col] && !mark[next_row][next_col] )
                {
                mark[next_row][next_col] = 1; // 방문표시
                position.row = row;
                position.col = col;
                position.dir = ++dir;
                add(&top, position);
                row = next_row;
                col = next_col;
                dir = 0;
                }
			else ++dir;
		}
	}
    if ( found ) {
        printf("< Path >\n");
        printf("row col\n");
        for ( i = 0; i <= top; i++ )
            printf("%2d%5d", stack[i].row, stack[i].col);
            printf("%2d%5d\n", row, col);
            printf("%2d%5d\n", EXIT_ROW, EXIT_COL);
    }
    else printf("경로 없음!!\n");
}

 

으엌 코드가 길어지면서 내 머리도 터져버렸다.

미로 유사 코딩으로부터 위와 같은 식을 도출해보았다. 쉽지는 않지만 이전의 알고리즘과 유사코딩을 따라오다보면 슬금슬금 풀려진다.