오랜만에 헬프를 칩니다 ;ㅅ;

혹시 프로그래밍이나 뭐 알고리즘 같은거 배우신분은 도움 좀 주세요.

 

사각형의 벽 외곽에 출구와 입구가 있는 미로는 오른손의 법칙으로 출구를 찾는 방법을 사용할 수 있습니다. 그런데 공터의 한가운데에 미로의 출구가 있고 외곽에 입구가 있는 경우엔 오른손의 법칙으로는 영영 출구를 찾을 수가 없잖아요?

 

탈출거리를 최소화한다거나 하는것까진 바라진 않지만 어쨌든 이런 상황에서 출구를 찾는 방법을 알고 싶습니다. 백트래킹이란 방법이 있다고 해서 이것저것 찾아봤는데 그걸 어떤식으로 적용해서 풀어야 될지 잘 떠오르지가 않네요.. 두방향 이상으로 길이 뚫려있을경우 위치를 계속 기억해두고 일단 가본후에 막혀있으면 최근 분기점으로 돌아오고 또 막히면 또 그 전의 분기점으로 돌아오라고 하는데 이게 개념상으로는 이해가 되도 변수나 알고리즘을 어떤식으로 짜야할지 잘 감이안옵니다 ;ㅅ;

미로라고하니 라인트레이서가생각이나네

???????이건 어느나라에서쓰는 언어이지??????

저게 어디에 쓰이는지도 모르겠음

으악 ㅠㅠ 대체 무슨맵을 만드시길래 ㄷㄷㄷ

// 미로 세팅, 일단 20*20 배열
// 벽은 1, 빈공간은 0
int maze[20][20];
int end_x = 10, end_y = 10;
// 도착 장소는 10,10

// 미로 찾기
int count_prev = 400;
find(int x, int y, int a, int c) {
// 매개변수 a는 자기가 온 방향
// 1은 →, 2는 ↑, 3은 ↓, 4는 ←
// 매개변수 c는 시작지점 부터 몇칸인지

int i,j;

if(x = end_x && y = end_y) {
if(c < count_prev) {
count_prev = c;
} else {
// 경로 비용이 이전 경호 비용보다 크면
// 온 방향을 막아버림
if(a == 1) {
maze[x-1][y] = 1;
} else if(a == 2) {
maze[x][y-1] = 1;
} else if(a == 3) {
maze[x][y+1] = 1;
} else if(a == 4) {
maze[x+1][y] = 1;
}
}
} else {
if(maze[x+1][y] == 0 && a != 1) {
// → 이쪽 방향 뚫렸을 경우
count++;
find(maze, x+1, y, 1, c+1);
}
if(maze[x][y+1] == 0 && a != 2) {
// ↑ 이쪽 방향 뚫렸을 경우
count++;
find(maze, x, y+1, 2, c+1);
}
if(maze[x][y-1] == 0 && a != 3) {
// ↓ 이쪽 방향 뚫렸을 경우
count++;
find(maze, x, y-1, 3, c+1);
}
if(maze[x-1][y] == 0 && a != 4) {
// ← 이쪽 방향 뚫렸을 경우
count++;
find(maze, x-1, y, 4, c+1);
}

maze[x][y] = 1;
// 막혔으면, 경로를 지움
}
}

void main() {
find(0,0,0,0);
}

...급하게 생각해본건데, 컴파일러 없어서 확인은 못해보겠네요..
재귀함수로 마치 트리를 만드는것 처럼 뚫린방향으로 쭉쭉 뻗어나갑니다.
재귀 함수가 끝나고 나면 maze[20][20] 변수에 최소 경로만 0으로 남습니다..(제대로 된다면)

ㄴ 긴설명 감사합니다-
근데 드론이랑 얘기해본결과 텅빈 메이즈에서 출구를 못찾고 빙빙도는건 어떻게 안되는것같다고해서.. 변수에 이동경로를 저장하느니마느니 하고 한참 고민을 해봤는데 아무래도 그냥 다른 방식으로 해결해야할것 같습니다..
이 방법을 쓰려던 이유가 맵의 난이도를 어떻게 좀 낮춰보려는 의도였거든요.. 그냥 제가 이러는게 마치 "저 오늘 갤디터 처음 열어봤는데 메탈슬러그가 멋있어 보이더라구요 횡스크롤로 움직이면서 우클릭으로 점프하고 좌클릭한 지점으로 미사일쏘는 게임을 만들려고 하는데 차근차근 알려주시면 감사하겠습니다"라고 묻는것같아서....
그냥 다른 방식으로 난이도를 조절하겠습니다요 ㄱ-..

ㄴ 듣고보니 빙빙 도는건 생각도 못했네요 ㄷㄷ

헐 Guetelperr 님이 헬프를 치시다니;;;;;;역시 갤디터의 벽이란...