10.3.2 깊이 우선 탐색(인접 행렬) 구현

이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다.

깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다.

그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요.

다음은 스택을 이용한 깊이 우선 탐색 알고리즘의 의사코드예요.

원본 그래프와 출발지, 목적지를 설정한 초기 경험 정보를 생성

스택에 보관

반복(스택이 비어 있지 않다면)

    스택에서 경험 정보 꺼내옮

    스택에서 꺼내온 경험 정보에서 다음 경험(이웃을 방문하는) 목록 조사

    반복(다음 경험 목록을 순차적으로 반복)

        목적지에 도달하면

            결과 출력

        그렇지 않다면

            스택에 보관

여기에서는 출발지와 목적지까지 갈 수 있는 모든 경로를 찾기로 할게요.

먼저 경험한 정점을 보관하는 벡터를 Foots로 정의할게요.

그리고 경험 정보를 보관하는 벡터를 Heues라고 정합시다.

Heuristic 클래스를 정의하세요.

원본 그래프와 목적지와 경험한 정점을 보관한 벡터가 멤버로 필요하겠죠.

생성자는 그래프와 출발지과 목적지를 입력 인자로 받아야겠죠.

현재 경험에서 이웃하는 정점을 방문하는 다음 경험 목록을 조사하는 메서드가 필요합니다.

목적지에 도달했는지 판별하는 메서드와 현재까지 경로를 출력하는 메서드를 제공합시다.

이전 경험에서 특정 정점을 추가 방문하는 생성자를 제공하세요.

생성자를 구현합시다.

그래프를 설정하고 시작 정점을 방문합니다. foots는 방문한 정점을 보관하는 컬렉션입니다.

그리고 목적지를 설정하세요.

현재 경험에서 이웃하는 정점을 방문하는 경험 목록을 구하는 메서드를 구현합시다.

가장 최근에 방문한 정점을 구하여 이웃하는 정점 목록을 구하세요.

이웃 정정을 순차적으로 순회하며 새로운 경험 목록에 추가할 것인지 결정합니다.

이웃하는 정점에 방문한 적이 없으면 새로운 경험을 생성하여 새로운 경험 목록에 추가하세요.

마지막 방문지가 목적지와 같은지 판별하는 메서드를 구현하세요.

현재까지의 행적을 출력하는 메서드를 구현하세요.

이전 경험에서 새로운 정점을 추가하는 생성자를 구현하세요.

이제 테스트 코드를 작성합시다.

테스트에 사용할 그래프를 생성하고 보여주는 코드는 이전 게시글(그래프 구현)과 같습니다.

경험 정보를 보관할 스택이 필요하죠.

초기 경험 정보를  생성하여 스택에 보관하세요.

스택이 빌 때까지 반복합니다.

스택에서 경험 정보를 꺼내오세요.

현재 경험 정보를 출력하여 어떻게 진행하는지 확인합시다.

스택에서 꺼내온 경험 정보에서 다음 경험 목록을 조사하세요.

조사한 다음 경험 목록을 순차적으로 방문합니다.

만약 목적지에 도달하였으면 원하는 솔루션입니다.

솔루션의 결과를 출력하세요.

더 이상 필요없는 경험 정보는 소멸해야겠죠.

그렇지 않다면 다시 스택에 보관하세요.

더 이상 필요없는 경험 정보는 소멸하세요.

다음은 방향성있는 그래프에서 실행한 결과입니다.방향성 있는 그래프와 인접 행렬

▷ 실행 결과

다음은 방향성없는 그래프에서 실행한 결과입니다.방향성 없는 그래프와 인접 행렬

▷ 실행 결과

이상으로 인접 행렬로 그래프를 표현하고 그래프에서 경로를 찾는 깊이 우선 탐색 알고리즘 구현을 마칠게요. 앞에서도 얘기했듯이 인접 행렬로 그래프를 표현할 때는 정점의 개수가 적을 때 사용하세요. 정점의 개수가 많아지면 필요없는 간선 정보가 기하급수적으로 늘어나 성능에 문제가 발생합니다.

이 책에서는 바로 이어서 그래프를 정점과 간선의 집합으로 표현하는 방법을 다룰거예요. 구현 비용은 인접 행렬로 구현하는 것보다 많이 들지만 정점의 개수가 많아졌을 때 인접 행렬로 표현한 것보다 성능이 좋아집니다.


실습한 결과물은 언제나 휴일 프로그램 소스 사이트에 있습니다.