1. maze
교재 Program 3.12의 함수 path를 아래 요건대로 수정한 후 이를 호출하여 경로찾기를 수행하고 경로
를 출력하는 maze 프로그램을 작성하시오.
- mark[][] 배열을 사용하지 않는다.
- maze[][] 배열의 상하좌우 가장자리 element들을 사용하지 않는다. 즉, n by m maze의 경우 교재의 프로그램에서는 maze[][] 배열을 maze[n+2][m+2] 로 선언하고 상하좌우 가장자리 element들의 값을1로 설정하여 사용하는데 본 수정에서는 maze[][] 배열을 maze[n][m]로 선언하여 maze를 표현한다.
- stack에 저장 시 위치좌표만 저장하고 방향정보는 저장하지 않는다. 즉, 교재에서는 (row, col, dir)을 push하는데 (row, col) 만 push한다.
- 출구좌표에 도달했는지의 체크를 현재 위치좌표가 출구좌표와 동일한지를 확인하는 것으로 수행하도록 한다. 교재에서는 현재 위치좌표가 출구좌표의 바로 이웃 위치좌표인가를 확인하는 것으로 수행하고
있다.
데이터 입력 :
아래와 같이 한다. define문의 설정값 및 maze[][] 배열의 값은 아래 예시로 한정하지 않고 임의의 값으로 변경 가능하도록 한다. 단, maze 크기에 따라 stack_size는 overflow가 발생하지 않도록 충분히 잡는다. 채점 시 아래 라인들을 값만 변경된 라인들로 대체하고 컴파일 및 실행한다.
#define numRow 10
#define numCol 10
#define stack_size 100
int maze[numRow][numCol] = {
{ 0,0,1,0,1,1,1,0,1,0 },
{ 1,0,0,1,1,1,0,1,0,1 },
{ 1,1,0,1,1,0,1,0,1,1 },
{ 0,0,1,0,1,1,1,0,0,0 },
{ 0,1,1,0,1,0,1,0,1,0 },
{ 1,0,1,1,1,1,0,0,1,0 },
{ 1,1,0,1,0,1,0,0,1,0 },
{ 1,0,0,0,1,0,1,0,0,0 },
{ 0,1,0,1,1,1,0,1,1,0 },
{ 1,0,0,1,1,1,0,0,0,0 }
};
1) 알고리즘 설명 : 우선 현재 좌표 위치를 stack에서 pop한다. (초기 값은 0, 0) 현쟂의 좌표는 path_flag를 1로 설정한다. (지나간 길임을 나타내 주는 것) move 배열에 있는 방향 순서대로 현재 좌표 기준 legal path를 같은 stack에 저장한다. (갈림길에서의 다른 경우의 수 저장) 가장 최근 저장한 legal path로 이동하고, 길이 없을 경우 지나온 좌표들 (path_flag == 1)을 stack에서 삭제, 최근 갈림길의 다른 경우의 수 (path_flag == 0)로 이동한다.
2) 조건 충족 여부
- mark 배열을 사용하는 대신, 미로를 나타내는 maze 배열을 직접적으로 변경하였다. 지나간 곳은 0을 1로 바꾸어 벽처럼 취급하였고, 잘못된 길로 가서 다시 돌아와야 하는 경우에는 가장 최근 갈림길로 돌아와 stack에 저장된 다른 길로 가도록 설정하였다.
maze[row][col] = 1;대신, stack에 갈림길 정보도 함께 저장하기 때문에, 직접 밟은 기록과 갈림길 정보는 flag로 구분하였다. (조건대로 dir 정보는 push하지 않기 때문에, 다른 배열(mark 용이 아닌 print를 위한)로 저장 가능, 조건 충족)
row = position.row; col = position.col;
position.path_flag = 1;
push(position);
- 상하좌우에 1로 만든 벽을 세우지 않고, legal path의 조건에 배열 범위 내에 index를 갖도록 조건을 추가하였다.
else if (!maze[nextRow][nextCol] && nextRow > -1 && nextCol > -1 && nextRow < numRow && nextCol < numCol)
- 방향 정보를 저장하지 않고, 각각의 좌표에 대해 legal한 path를 전부 미리 검사하여 stack에 쌓아둔다.
position.row = nextRow; position.col = nextCol; position.path_flag = 0;
push(position);
cnt++;
- D 조건대로 변경
if (row == EXIT_ROW && col == EXIT_COL) {
found = TRUE;}
#include <stdio.h>
#define numRow 10
#define numCol 10
#define stack_size 100
#define EXIT_ROW 9
#define EXIT_COL 9
#define TRUE 1
#define FALSE 0
typedef struct {
short int vert;
short int horiz;
} offsets;
typedef struct {
short int row;
short int col;
short int path_flag; // 프린트 할 요소 flag
} element;
int maze[numRow][numCol] = {
{0,0,1,0,1,1,1,0,1,0},
{1,0,0,1,1,1,0,1,0,1},
{1,1,0,1,1,0,1,0,1,1},
{0,0,1,0,1,1,1,0,0,0},
{0,1,1,0,1,0,1,0,1,0},
{1,0,1,1,1,1,0,0,1,0},
{1,1,0,1,0,1,0,0,1,0},
{1,0,0,0,1,0,1,0,0,0},
{0,1,0,1,1,1,0,1,1,0},
{1,0,0,1,1,1,0,0,0,0}
};
offsets move[8] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };
element stack[stack_size+1];
int top = 0;
element push(element val)
{
if (top >= stack_size - 1) {
printf("Stack Overflow.");
}
stack[++top] = val;
return val;
}
element pop(void) {
if (top < 0) {
printf("Stack Underflow.");
}
int pop = top--;
return stack[pop];
}
void path(void)
{
int i, row, col, nextRow, nextCol, dir, cnt, found = FALSE;
element position, flag;
dir = 0;
position.row = 0; position.col = 0; position.path_flag = 1;
push(position);
while (top > -1 && !found) {
position = pop();
row = position.row; col = position.col;
position.path_flag = 1;
push(position);
cnt = 0;
while (dir < 8 && !found) {
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;
if (row == EXIT_ROW && col == EXIT_COL) {
found = TRUE;
}
else if (!maze[nextRow][nextCol] && nextRow > -1 && nextCol > -1 && nextRow < numRow && nextCol < numCol) {
position.row = nextRow; position.col = nextCol; position.path_flag = 0;
push(position);
cnt++;
}
dir++;
}
if (!cnt) {
while (1) {
flag = pop();
if (flag.path_flag == 0) {
push(flag);
break;
}
}
}
dir = 0;
maze[row][col] = 1;
}
if (found) {
printf("The path is: \n");
printf("row col\n");
for (i = 0; i <= top; i++) {
if (stack[i].path_flag) printf("%2d %5d\n", stack[i].row, stack[i].col);
}
printf("%2d %5d\n", row, col);
}
else printf("The maze does not have a path \n");
}
int main()
{
path();
return 0;
}
출구까지 모든 지나간 길을 출력, 방향 우선순위는 교재의 반대이다.
<알고리즘 설명>
그림 1~8은 문제에서 주어진 예시 maze의 왼쪽 상단이다.
그림 1 : 프로그램 시작 시점에서는, 출발점의 좌표가 stack에 들어있다. path()함수는 항상 stack의 top으로 이동한다. stack의 top에 있는 ①좌표로 이동한다.
그림 2 : pop 한 좌표로 이동한 후, path_flag를 1로 바꾸어 다시 push한다.
그림 3 : 현재 위치에서 갈 수 있는 좌표 ②, ③을 모두 stack에 push한다. 이 때에는 path_flag를 0으로 저장하여 '실제 간 길'이 아닌 '갈 수 있던 길'임을 구분한다. 이동 하기 전 현재 위치는 0 -> 1로, 즉 벽으로 변경한다. (그림 4에서 색칠하여 표기)
(반복)
그림 4 : 방금 저장한 '갈 수 있던 길' 중 가장 위에 있는 top에 해당하는 좌표를 pop하여 위치(③)로 이동한다. 실제로 간 길이 되었으므로 path_flag를 1로 바꾼다.
그림 5 : flag를 1로 바꾼 좌표를 다시 stack에 push한다.
그림 6 : 현재 위치에서 갈 수 있는 좌표 ②, ④, ⑤를 모두 stack에 push한다. path_flag는 0.
그림 7 : 현재 위치를 벽으로 색칠하고, stack의 top을 pop 하여 해당 위치 ⑤로 이동한다.
(반복)
그림 8 : 다시 flag를 1로 바꾸어 push하고 있다.
기본 원리는 위와 같다. 계속하여 반복 진행 하면, stack 안에 flag가 1인 요소들 사이사이에 0인 요소들이 들어 있고, 이는 0인 요소들 중 바로 위 1을 선택했음을 읽을 수 있게 해준다. 이를 활용하여 막다른 길에 다다랐을 때 backtrack을 실행할 수 있다.
그림 9~14은 문제에서 주어진 예시 maze의 왼쪽 하단이다.
그림 9 : 앞서 소개한 알고리즘에 따라 미로를 이동하다 보면, 위와 같이 ①로 이동하게 된다.
그림 10 : 반복 시행을 통해 이동하고, stack에 좌표가 저장된 모습이다.
그림 11 : 다시 한 번 더, ⑦에서 이동하기 위해 가능한 위치를 찾아 stack에 저장하고, top에 해당하는 ④로 이동했다.
그림 12 : 같은 시행을 통해 ④에서 ⑪,⑤ 중 top에 해당하는 ⑤로 이동하였지만, 더 이상 갈 수 없는 길이 된다.
그림 13 : 막다른 길에 다다른 경우, stack에서 path_flag가 1인 좌표들을 모두 pop하여 지운다. (간 길 취소)
그림 14 : pop한 좌표가 path_flag가 0이라면, 실제 갔던 길이 아닌 갈 수 있던 다른 길이므로 다시 push하여 다음 반복 때 해당 좌표로 이동하도록 한다.
0이 나올 때까지 pop을 할 때, path_flag가 1인 좌표가 연달아 많이 나오더라도, pop을 통해 stack에서 완전히 제거하고, 또 어차피 '잘못 들어선 길'이기 때문에 벽을 다시 길로 바꾸는 연산은 불필요하다.
종료 지점에 도착하면, stack에서 path_flag가 1인 좌표들만 출력하여 길을 나타낼 수 있다.
'College Computer Science > Data Structure' 카테고리의 다른 글
| [자료구조 프로그래밍 연습문제] 연결 리스트 (linked list) invert 함수, 원형 연결 리스트 (circular linked list) (0) | 2022.01.12 |
|---|---|
| [자료구조 프로그래밍 연습문제] 다항식 덧셈, 희소행렬 덧셈 (0) | 2022.01.12 |
| [자료구조 프로그래밍 연습문제] 희소행렬 전치 (0) | 2022.01.11 |
| [자료구조 프로그래밍 연습문제] 다항식 계수 배열, 다항식 곱하기, 구조체 (0) | 2022.01.11 |
| [자료구조 프로그래밍 연습문제] 재귀함수, 선택정렬, 배열 (0) | 2022.01.10 |
댓글