해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.
조건
- 1은 경로, 0은 벽
- 이동은 우, 우하, 하, 좌하, 좌, 좌상, 상, 우상의 순으로 1을 만나면 전진
- 입구: (0,0), 출구: (10,15)
문제
- 미로에 대하여 '*'로 출력하시오.
문제 해결
- 입구에서 1을 따라 전진하다가 막히면 이전으로 돌아가서 다음 방향을 살펴 봄
- 이전으로 돌아가기 위하여 스택 구조를 사용함
- 전진: 이동 방향을 찾았으면 현재 위치의 행과 열, 이동할 방향의 다음 방향을 stack 배열에 push()하고 전진한다.
- 후진: 현재 위치에서 더 이상 전진할 곳이 없으면 stack의 top 위치에 있는 행, 열, 방향을 pop()하여 그 위체에서 다시 탐색한다.ㅣㅐ
유의 사항
- 탐색한 미로는 표시하여 재탐색하지 않도록 함
실습
#include <stdio.h>
#define M 12
#define N 16
#define MAX M*N
enum boolean{false,true};
int top = -1;
int stack[MAX][3] = {0,}
enum boolean push(int x, int y, int d){
if(top >= MAX-1){
printf("Stack overflow\n");
return false;
}
top = top + 1;
stack[top][0] = x;
stack[top][1] = y;
stack[top][2] = d;
return true;
}
enum boolean pop(int *x, int *y, int *d){
if(top == -1){
printf("stack underflow\n");
return false;
}
*x = stack[top][0];
*y = stack[top][1];
*d = stack[top][2];
top = top -1;
return true;
}
// 미로 탐색
