이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다.
깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다.
그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요.
다음은 스택을 이용한 깊이 우선 탐색 알고리즘의 의사코드예요.
원본 그래프와 출발지, 목적지를 설정한 초기 경험 정보를 생성
스택에 보관
반복(스택이 비어 있지 않다면)
스택에서 경험 정보 꺼내옮
스택에서 꺼내온 경험 정보에서 다음 경험(이웃을 방문하는) 목록 조사
반복(다음 경험 목록을 순차적으로 반복)
목적지에 도달하면
결과 출력
그렇지 않다면
스택에 보관
여기에서는 출발지와 목적지까지 갈 수 있는 모든 경로를 찾기로 할게요.
먼저 경험한 정점을 보관하는 벡터를 Foots로 정의할게요.
typedef vector<int> Foots; typedef Foots::iterator FIter; typedef Foots::const_iterator CFIter;
그리고 경험 정보를 보관하는 벡터를 Heues라고 정합시다.
class Heuristic; typedef vector<Heuristic *> Heues; typedef Heues::iterator HIter; typedef Heues::const_iterator CHIter;
Heuristic 클래스를 정의하세요.
class Heuristic
{
원본 그래프와 목적지와 경험한 정점을 보관한 벡터가 멤버로 필요하겠죠.
Graph *graph;
int goal;
Foots foots;
생성자는 그래프와 출발지과 목적지를 입력 인자로 받아야겠죠.
public:
Heuristic(Graph *graph, int start,int goal);
현재 경험에서 이웃하는 정점을 방문하는 다음 경험 목록을 조사하는 메서드가 필요합니다.
Heues EnumNext();
목적지에 도달했는지 판별하는 메서드와 현재까지 경로를 출력하는 메서드를 제공합시다.
bool IsGoal()const;
void View()const;
이전 경험에서 특정 정점을 추가 방문하는 생성자를 제공하세요.
private:
Heuristic(const Heuristic *bheu,int vt);
};
생성자를 구현합시다.
Heuristic::Heuristic(Graph *graph,int start,int goal)
{
그래프를 설정하고 시작 정점을 방문합니다. foots는 방문한 정점을 보관하는 컬렉션입니다.
this->graph = graph;
foots.push_back(start);
그리고 목적지를 설정하세요.
this->goal = goal; }
현재 경험에서 이웃하는 정점을 방문하는 경험 목록을 구하는 메서드를 구현합시다.
Heues Heuristic::EnumNext()
{
Heues nheues;
가장 최근에 방문한 정점을 구하여 이웃하는 정점 목록을 구하세요.
//가장 최근에 방문한 정점
int last_foot = (*foots.rbegin());
//마지막 방문 정점의 이웃하는 정점을 구함
Neighbors neighbors = graph->FindNeighbors(last_foot);
이웃 정정을 순차적으로 순회하며 새로운 경험 목록에 추가할 것인지 결정합니다.
Neighbors neighbors = graph->FindNeighbors(last_foot);
FIter seek = neighbors.begin();
FIter last = neighbors.end();
for( ;seek != last; ++seek)
{
이웃하는 정점에 방문한 적이 없으면 새로운 경험을 생성하여 새로운 경험 목록에 추가하세요.
if(find(foots.begin(), foots.end(),*seek) == foots.end())//방문한 적이 없으면
{
nheues.push_back(new Heuristic(this,*seek));//*seek를 추가 방문하는 새로운 경험을 생성
}
}
return nheues;
}
마지막 방문지가 목적지와 같은지 판별하는 메서드를 구현하세요.
bool Heuristic::IsGoal()const
{
return (*foots.rbegin()) == goal;
}
현재까지의 행적을 출력하는 메서드를 구현하세요.
void Heuristic::View()const
{
cout<<"Foots: ";
CFIter seek = foots.begin();
CFIter last = foots.end();
for( ;seek != last; ++seek)
{
cout<<(*seek)<<" ";
}
cout<<endl;
}
이전 경험에서 새로운 정점을 추가하는 생성자를 구현하세요.
Heuristic::Heuristic(const Heuristic *bheu,int vt)
{
this->graph = bheu->graph;
foots = bheu->foots;
this->goal = bheu->goal;
//새로운 정점을 방문한 정점을 보관하는 foots에 추가하세요.
foots.push_back(vt);//vt를 방문한 행적에 추가
}
이제 테스트 코드를 작성합시다.
int main()
{
테스트에 사용할 그래프를 생성하고 보여주는 코드는 이전 게시글(그래프 구현)과 같습니다.
Graph *graph = new Graph(9);//그래프 동적 생성
graph->AddEdge(0, 1);//간선 추가
...생략...
graph->ViewNeighbors();
경험 정보를 보관할 스택이 필요하죠.
stack<Heuristic *> hs;
초기 경험 정보를 생성하여 스택에 보관하세요.
Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성
hs.push(heu);//스택에 보관
스택이 빌 때까지 반복합니다.
while(hs.empty() == false) //반복(스택이 비어 있지 않다면)
{
스택에서 경험 정보를 꺼내오세요.
heu = hs.top();//스택에서 경험 정보 꺼내옮
hs.pop();
현재 경험 정보를 출력하여 어떻게 진행하는지 확인합시다.
heu->View();
스택에서 꺼내온 경험 정보에서 다음 경험 목록을 조사하세요.
Heues nheues = heu->EnumNext();//스택에서 꺼내온 경험 정보에서 다음 경험 목록 조사
조사한 다음 경험 목록을 순차적으로 방문합니다.
HIter seek = nheues.begin();
HIter last = nheues.end();
for( ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)
{
만약 목적지에 도달하였으면 원하는 솔루션입니다.
if((*seek)->IsGoal())//목적지에 도달하면
{
솔루션의 결과를 출력하세요.
cout<<"솔루션 ";
(*seek)->View();//결과 출력
더 이상 필요없는 경험 정보는 소멸해야겠죠.
delete (*seek);
}
그렇지 않다면 다시 스택에 보관하세요.
else//그렇지 않다면
{
hs.push(*seek);//스택에 보관
}
}
더 이상 필요없는 경험 정보는 소멸하세요.
delete heu;
}
return 0;
}
다음은 방향성있는 그래프에서 실행한 결과입니다.
▷ 실행 결과
=== 이웃 정점 === 0의 이웃: 1 2 1의 이웃: 2 3 2의 이웃: 4 3의 이웃: 6 4의 이웃: 5 6 7 5의 이웃: 6의 이웃: 8 7의 이웃: 8의 이웃: Foots: 0 Foots: 0 2 Foots: 0 2 4 Foots: 0 2 4 7 Foots: 0 2 4 6 솔루션 Foots: 0 2 4 6 8 Foots: 0 2 4 5 Foots: 0 1 Foots: 0 1 3 Foots: 0 1 3 6 솔루션 Foots: 0 1 3 6 8 Foots: 0 1 2 Foots: 0 1 2 4 Foots: 0 1 2 4 7 Foots: 0 1 2 4 6 솔루션 Foots: 0 1 2 4 6 8 Foots: 0 1 2 4 5
다음은 방향성없는 그래프에서 실행한 결과입니다.
▷ 실행 결과
=== 이웃 정점 === 0의 이웃: 1 2 1의 이웃: 0 2 3 2의 이웃: 0 1 4 3의 이웃: 1 6 4의 이웃: 2 5 6 7 5의 이웃: 4 6의 이웃: 3 4 8 7의 이웃: 4 8의 이웃: 6 Foots: 0 Foots: 0 2 Foots: 0 2 4 Foots: 0 2 4 7 Foots: 0 2 4 6 솔루션 Foots: 0 2 4 6 8 Foots: 0 2 4 6 3 Foots: 0 2 4 6 3 1 Foots: 0 2 4 5 Foots: 0 2 1 Foots: 0 2 1 3 Foots: 0 2 1 3 6 솔루션 Foots: 0 2 1 3 6 8 Foots: 0 2 1 3 6 4 Foots: 0 2 1 3 6 4 7 Foots: 0 2 1 3 6 4 5 Foots: 0 1 Foots: 0 1 3 Foots: 0 1 3 6 솔루션 Foots: 0 1 3 6 8 Foots: 0 1 3 6 4 Foots: 0 1 3 6 4 7 Foots: 0 1 3 6 4 5 Foots: 0 1 3 6 4 2 Foots: 0 1 2 Foots: 0 1 2 4 Foots: 0 1 2 4 7 Foots: 0 1 2 4 6 솔루션 Foots: 0 1 2 4 6 8 Foots: 0 1 2 4 6 3 Foots: 0 1 2 4 5
이상으로 인접 행렬로 그래프를 표현하고 그래프에서 경로를 찾는 깊이 우선 탐색 알고리즘 구현을 마칠게요. 앞에서도 얘기했듯이 인접 행렬로 그래프를 표현할 때는 정점의 개수가 적을 때 사용하세요. 정점의 개수가 많아지면 필요없는 간선 정보가 기하급수적으로 늘어나 성능에 문제가 발생합니다.
이 책에서는 바로 이어서 그래프를 정점과 간선의 집합으로 표현하는 방법을 다룰거예요. 구현 비용은 인접 행렬로 구현하는 것보다 많이 들지만 정점의 개수가 많아졌을 때 인접 행렬로 표현한 것보다 성능이 좋아집니다.