[Location2D.h]
/*
미로 탐색을 위한 2차원 좌표 클래스
*/
struct Location2D
{
int row; //현재 위치의 행 번호
int col; //현재 위치의 열 벊호
Location2D(int r = 0, int c = 0)
{
row = r;
col = c;
}
//위치 p가 자신의 이웃인지 검사하는 함수
bool isNeighbor(Location2D &p)
{
return ((row == p.row && (col == p.col - 1 || col == p.col + 1)) || (col == p.col && (row == p.row - 1 || row == p.row + 1)));
}
//위치 p가 자신과 같은 위치인지를 검사하는 함수(연산자 오버로딩 사용)
bool operator==(Location2D &p)
{
return row == p.row && col == p.col;
}
};
[Maze.h]
/*
2차원 배열의 동적 할당과 해제를 이용하여 3.5절에서 소개한 미로 탐색 문제를 다음과 같이 보완하라
(1) 미로 탐색을 위한 클래스 Maze를 구현하라
(2) 다음과 같은 전체 프로그램을 구현하라
*/
#include <iostream>
#include <fstream>
#include "Location2D.h"
#include <stack>
using namespace std;
class Maze
{
private:
int width; //미로의 너비
int height; //미로의 높이
int **map; //미로 맵
stack<Location2D> locStack; //스택
Location2D exitLoc; //미로의 출구
public:
Maze()
{
init(0, 0);
}
~Maze()
{
reset();
}
void init(int w, int h) //map 이차원 배열을 동적으로 할당
{
map = new int*[h];
for (int i = 0; i < h; i++)
map[i] = new int[w];
}
void reset() //미로 맵 maze를 동적으로 해제
{
for (int i = 0; i < height; i++)
delete[]map[i];
delete[]map;
}
void load(char *fname) //파일에서 미로 파일을 읽어옴
{
ifstream fin(fname, ios::in);
fin >> width >> height;
init(width, height);
int temp;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
fin >> temp;
map[i][j] = temp;
if (map[i][j] == 5)
{
Location2D entry(j, i);
locStack.push(entry);
}
else if (map[i][j] == 9)
{
exitLoc.col = i;
exitLoc.row = j;
}
}
cout << endl;
}
fin.close();
}
bool isValidLoc(int r, int c)
{
if (r < 0 || c < 0 || r >= 20 || c >= 10) //범위를 벗어나면 갈 수 없다
return false;
else //비어있는 통로나 도착지점일 때만 true
return (map[c][r] == 1 || map[c][r] == 9);
}
void print() //현재 Maze를 화면에 출력
{
cout << "전체 미로의 크기 = " << height << " * " << width << endl;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
if (map[i][j] == 1)
{
cout << " ";
}
else if (map[i][j] == 0)
{
cout << "■";
}
else if (map[i][j] == 7)
{
cout << "□"; //지나온 경로
}
else if (map[i][j] == 5)
{
cout << "○";
}
else if (map[i][j] == 9)
{
cout << "◎";
}
}
cout << endl;
}
cout << endl;
}
void searchExit() //실제 미로를 탐색하는 함수
{
while (locStack.empty() == false) //스택이 비어있지 않는 동안
{
Location2D here = locStack.top(); //스택에 상단 객체 복사
locStack.pop();
int r = here.row;
int c = here.col;
map[c][r] = 7; //시작점은 최적 경로
if (exitLoc.col==c && exitLoc.row==r)
{
return;
}
else
{
map[c][r] = 7; //지나온 곳으로 표기
//갈 수 있는 곳 다 가본다
if (isValidLoc(r - 1, c))
{
locStack.push(Location2D(r - 1, c));
}
if (isValidLoc(r + 1, c))
{
locStack.push(Location2D(r + 1, c));
}
if (isValidLoc(r, c - 1))
{
locStack.push(Location2D(r, c - 1));
}
if (isValidLoc(r, c + 1))
{
locStack.push(Location2D(r, c + 1));
}
}
}
}
};
[MazeMain.cpp]
#include "Maze.h"
int main(void)
{
Maze maze; //미로 탐색 객체 생성
maze.load("C:\\Maze.txt");
maze.print();
maze.searchExit(); //미로를 탐색해 출구를 찾음
maze.print();
return 0;
}
[Maze.h 최적경로 추가 버전]
/*
2차원 배열의 동적 할당과 해제를 이용하여 3.5절에서 소개한 미로 탐색 문제를 다음과 같이 보완하라
(1) 미로 탐색을 위한 클래스 Maze를 구현하라
(2) 다음과 같은 전체 프로그램을 구현하라
*/
#include <iostream>
#include <fstream>
#include "Location2D.h"
#include <stack>
using namespace std;
class Maze
{
private:
int width; //미로의 너비
int height; //미로의 높이
int **map; //미로 맵
stack<Location2D> locStack; //스택
stack<Location2D> optimum; //최적경로
Location2D exitLoc; //미로의 출구
public:
Maze()
{
init(0, 0);
}
~Maze()
{
reset();
}
void init(int w, int h) //map 이차원 배열을 동적으로 할당
{
map = new int*[h];
for (int i = 0; i < h; i++)
map[i] = new int[w];
}
void reset() //미로 맵 maze를 동적으로 해제
{
for (int i = 0; i < height; i++)
delete[]map[i];
delete[]map;
}
void load(char *fname) //파일에서 미로 파일을 읽어옴
{
ifstream fin(fname, ios::in);
fin >> width >> height;
init(width, height);
int temp;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
fin >> temp;
map[i][j] = temp;
if (map[i][j] == 5)
{
Location2D entry(j, i);
locStack.push(entry);
optimum.push(entry); //최적경로 스택에도 입력
}
else if (map[i][j] == 9)
{
exitLoc.col = i;
exitLoc.row = j;
}
}
cout << endl;
}
fin.close();
}
bool isValidLoc(int r, int c)
{
if (r < 0 || c < 0 || r >= 20 || c >= 10) //범위를 벗어나면 갈 수 없다
return false;
else //비어있는 통로나 도착지점일 때만 true
return (map[c][r] == 1 || map[c][r] == 9);
}
bool isShortestPath(int r, int c) //최적경로를 사용할 때 쓰이는 함수
{
if (r < 0 || c < 0 || r >= 20 || c >= 10) //범위를 벗어나면 갈 수 없다
return false;
else
return (map[c][r] == 7 || map[c][r] == 9); //이미 찾은 경로이거나 출구일때만 true
}
void print() //현재 Maze를 화면에 출력
{
cout << "전체 미로의 크기 = " << height << " * " << width << endl;
for (int i = 0; i < height; i++)
{
for (int j = 0; j < width; j++)
{
if (map[i][j] == 1)
{
cout << " ";
}
else if (map[i][j] == 0)
{
cout << "■";
}
else if (map[i][j] == 3)
{
cout << "☆";
}
else if (map[i][j] == 7)
{
cout << "□"; //지나온 경로
}
else if (map[i][j] == 5)
{
cout << "○";
}
else if (map[i][j] == 9)
{
cout << "◎";
}
}
cout << endl;
}
cout << endl;
}
void searchExit() //실제 미로를 탐색하는 함수
{
while (locStack.empty() == false) //스택이 비어있지 않는 동안
{
Location2D here = locStack.top(); //스택에 상단 객체 복사
locStack.pop();
int r = here.row;
int c = here.col;
map[c][r] = 7; //시작점은 최적 경로
if (exitLoc.col == c && exitLoc.row == r)
{
return;
}
else
{
map[c][r] = 7; //지나온 곳으로 표기
//갈 수 있는 곳 다 가본다
if (isValidLoc(r - 1, c))
{
locStack.push(Location2D(r - 1, c));
}
if (isValidLoc(r + 1, c))
{
locStack.push(Location2D(r + 1, c));
}
if (isValidLoc(r, c - 1))
{
locStack.push(Location2D(r, c - 1));
}
if (isValidLoc(r, c + 1))
{
locStack.push(Location2D(r, c + 1));
}
}
}
}
void ShortestPath() //최적경로
{
while (!optimum.empty()) //구조는 searchExit()과 동일
{
Location2D here = optimum.top();
optimum.pop();
int r = here.row;
int c = here.col;
map[c][r] = 3;
if (exitLoc.col == c && exitLoc.row == r)
{
return;
}
else
{
map[c][r] = 3; //지나온 곳으로 표기
if (isShortestPath(r - 1, c))
{
optimum.push(Location2D(r - 1, c));
}
if (isShortestPath(r + 1, c))
{
optimum.push(Location2D(r + 1, c));
}
if (isShortestPath(r, c - 1))
{
if(!isShortestPath(r+1, c)) //오른쪽으로 가는 경로가 없을 경우 제외
optimum.push(Location2D(r, c - 1));
}
if (isShortestPath(r, c + 1))
{
if (!isShortestPath(r + 1, c) && !isShortestPath(r, c-1)) //오른쪽으로 가는 경로나 위쪽으로 가는 경로 둘 중 하나라도 있을시 제외
optimum.push(Location2D(r, c + 1));
}
}
}
}
};
[MazeMain.cpp]
#include "Maze.h"
int main(void)
{
Maze maze; //미로 탐색 객체 생성
maze.load("C:\\Maze.txt");
maze.print();
maze.searchExit(); //미로를 탐색해 출구를 찾음
maze.ShortestPath();
maze.print();
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
[참고] C++로 쉽게 풀어쓴 자료구조
*솔직히 최적경로 Maze.h는 특정미로에만 맞춰서 작성한것입니다.
*참고하여서 알맞게 수정하시길 바랍니다. 모든 미로에 대해 알맞게 작동하도록 추후 개선하도록 하겠습니다.
'C++ > C++로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 6 (6) | 2017.10.04 |
|---|---|
| C++로 쉽게 풀어쓴 자료구조 6장 연습문제 (0) | 2017.10.03 |
| C++로 쉽게 풀어쓴 자료구조 연습문제 4-8 (0) | 2017.09.27 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 4 (7) | 2017.09.27 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 3 (12) | 2017.09.23 |