C++의 미로 해결사
미로 해결 알고리즘은 컴퓨터 과학 및 인공 지능의 고전적인 문제입니다.
C++의 미로 해결사
미로 해결 알고리즘은 나침반의 네 방향으로만 이동하여 처음부터 끝까지 최단 경로를 찾는 것을 목표로 합니다. 알고리즘은 아직 방문하지 않은 모든 노드를 포함하는 열린 목록과 방문한 모든 노드를 포함하는 닫힌 목록의 두 가지 정보 집합을 유지합니다.
미로에서 한 노드에서 다른 노드로 가는 경로를 찾으려면 다음 작업을 수행해야 합니다.
-
열려 있는 노드가 현재 노드에 인접(왼쪽 또는 오른쪽)되어 있는지 확인합니다.
-
그렇지 않은 경우 닫힌 노드가 현재 노드에 인접(왼쪽 또는 오른쪽)되어 있는지 확인합니다.
-
그렇지 않은 경우 한 단계 뒤로 돌아가서 1단계와 2단계를 다시 수행하십시오.
미로 해결 알고리즘의 예:
#include <iostream>
using namespace std;
bool demo_maze(char maze[9][9], bool sam[9][9], int x, int y, int u, int v) {
if (x == u && y == v) {
sam[x][y] = true;
for (int t = 0; t <= u; t++) {
for (int f = 0; f <= v; f++) {
cout << sam[t][f] << " ";
}
cout << endl;
}
cout << endl;
return true;
}
if (x > u || y > v) return false;
if (maze[x][y] == 'X') return false;
sam[x][y] = true;
bool right = demo_maze(maze, sam, x, y + 1, u, v);
bool down = demo_maze(maze, sam, x + 1, y, u, v);
sam[x][y] = false;
if (right || down) return true;
return false;
}
int main() {
char maze[9][9] = {"0000", "00X0", "000X", "0X00"};
bool sam[9][9] = {0};
int u = 3, v = 3;
bool ans = demo_maze(maze, sam, 0, 0, u, v);
}
위에서 언급한 코드의 작동을 확인하려면 여기를 클릭하십시오.
C++에서 미로 해결사 사용
미로 해결 알고리즘은 체스, 지뢰 찾기, 지도에서 미로나 기타 장애물을 통과하는 경로 찾기 등 다양한 용도로 사용할 수 있습니다. 이 알고리즘은 숲이나 미로에서 길을 잃고 길을 찾을 때 어느 길로 가야할지 결정할 수 있습니다!
미로 해결 알고리즘은 2D 게임에도 사용되지만 계산 복잡성 때문에 다른 알고리즘보다 시간이 더 걸립니다. 플레이어의 좌표를 확인한 후 플레이어를 다음 지점으로 이동시키는 재귀 함수를 사용합니다.
재귀 함수는 직접 또는 간접적으로 자신을 호출합니다. 재귀의 문제를 푸는 데 사용할 수 있으며, 짧은 루프로 해가 쉽게 표현되지 않는 문제를 푸는 데도 사용할 수 있습니다.
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook