깊이우선 탐색과 너비우선 탐색입니다. 구현해보면 재미있으니 소스코드 참조하시기전에 먼저 책보고 한번 구현해보세요...
내가 풀어보고 남의 것을 보았을때 배울점이나 문제점을 잘 파악할 수 있는것 같습니다.
#include
#include
#include
#include
using namespace std;
void BreadthFirstSearch();
void DepthFirstSearch();
void PrintRoadMap(list roadMap);
int arr[9][9] = {
{0, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 1, 1, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 1, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 1, 0}
};
int main()
{
cout << "너비우선 탐색" << endl;
cout << "=> ";
BreadthFirstSearch();
cout << endl;
cout << "깊이우선 탐색" << endl;
cout << "=> ";
DepthFirstSearch();
cout << endl;
return 0;
}
void BreadthFirstSearch(){
queue dataQueue;
dataQueue.push(0);
list roadMap;
int chk[9] = {0};
int i=0;
chk[i] = 1;
while(dataQueue.size()){
i = dataQueue.front();
dataQueue.pop();
roadMap.push_back(i+1);
chk[i] = 1;
for(int j=0; j < 9; j++){
if(arr[i][j] == 1){
if(chk[j] == 0){
dataQueue.push(j);
chk[j] = 1;
}
}
}
}
PrintRoadMap(roadMap);
}
void DepthFirstSearch(){
stack dataStack;
dataStack.push(0);
list roadMap;
int chk[9] = {0};
int i=0;
chk[i] = 1;
while(dataStack.size()){
i = dataStack.top();
dataStack.pop();
roadMap.push_back(i+1);
chk[i] = 1;
for(int j=8; j > 0; j--){
if(arr[i][j] == 1){
if(chk[j] == 0){
dataStack.push(j);
chk[j] = 1;
}
}
}
}
PrintRoadMap(roadMap);
}
void PrintRoadMap(list roadMap){
list::iterator iter;
for(iter = roadMap.begin();iter != roadMap.end();iter++){
cout << *iter << " ";
}
}
