10 . 3 . 2 깊이 우선 탐색 ( 인접 행렬 ) 구현 – 언제나 휴일 
 이번 에 는 인접 행렬 로 구현 한 그래프 를 이용 하 여 깊이 우선 탐색 알고리즘 을 구현 해 봅시다 . 
 깊이 우선 탐색 은 한 정점 에서 갈 수 있 는 이웃 정점 으로 이동한 후 에 다시 이웃 정점 으로 이동 하 는 것 을 반복 합니다 . 단 이미 방문 한 정점 은 방문 하 지 않 으면서 목적지 까지 경로 를 찾 는 알고리즘 입니다 . 
 그런데 깊이 우선 탐색 에서 이동 하 다가 더 이상 갈 곳 이 없 으면 이전 갈림길 에서 다른 길 을 선택 할 수 있 어야 합니다 . 이 를 위해 현재 까지 이동한 경로 를 경험 정보 로 관리 하 고 한 정점 에서 갈 수 있 는 이웃 정점 을 추가 한 다음 경험 정보 를 스택 에 보관 해 두 었 다가 더 이상 갈 곳 이 없 으면 스택 에서 꺼내 와서 다른 경로 를 찾 게 구현 할 거 예요 . 
 다음 은 스택 을 이용 한 깊이 우선 탐색 알고리즘 의 의사 코드 예요 . 
 여기 에서 는 출발지 와 목적지 까지 갈 수 있 는 모든 경로 를 찾 기 로 할게요 . 
 먼저 경험 한 정점 을 보관 하 는 벡터 를 Foots 로 정의 할게요 . 
 그리고 경험 정보 를 보관 하 는 벡터 를 Heues 라고 정합시다 . 
 Heuristic 클래스 를 정의 하 세요 . 
 원본 그래프 와 목적지 와 경험 한 정점 을 보관 한 벡터 가 멤버 로 필요 하 겠 죠 . 
 생성자 는 그래프 와 출발지 과 목적지 를 입력 인자 로 받 아야 겠 죠 . 
 현재 경험 에서 이웃 하 는 정점 을 방문 하 는 다음 경험 목록 을 조사 하 는 메 서드 가 필요 합니다 . 
 목적지 에 도달 했 는지 판별 하 는 메 서드 와 현재 까지 경로 를 출력 하 는 메서 드 를 제공 합시다 . 
 이전 경험 에서 특정 정점 을 추가 방문 하 는 생성자 를 제공 하 세요 . 
 그래프 를 설정 하 고 시작 정점 을 방문 합니다 . foots 는 방문 한 정점 을 보관 하 는 컬렉션 입니다 . 
 그리고 목적지 를 설정 하 세요 . 
 현재 경험 에서 이웃 하 는 정점 을 방문 하 는 경험 목록 을 구하 는 메서 드 를 구현 합시다 . 
 가장 최근 에 방문 한 정점 을 구하 여 이웃 하 는 정점 목록 을 구하 세요 . 
 / / 가장 최근 에 방문 한 정점 
 / / 마지막 방문 정점 의 이웃 하 는 정점 을 구함 
 이웃 정정 을 순차 적 으로 순회 하 며 새로운 경험 목록 에 추가 할 것 인지 결정 합니다 . 
 이웃 하 는 정점 에 방문 한 적 이 없 으면 새로운 경험 을 생성 하 여 새로운 경험 목록 에 추가 하 세요 . 
 마지막 방 문지 가 목적지 와 같 은지 판별 하 는 메서 드 를 구현 하 세요 . 
 현재 까지 의 행적 을 출력 하 는 메서 드 를 구현 하 세요 . 
 이전 경험 에서 새로운 정점 을 추가 하 는 생성자 를 구현 하 세요 . 
 / / 새로운 정점 을 방문 한 정점 을 보관 하 는 foots 에 추가 하 세요 . 
 이제 테스트 코드 를 작성 합시다 . 
 테스트 에 사용 할 그래프 를 생성 하 고 보여 주 는 코드 는 이전 게시 글 ( 그래프 구현 ) 과 같 습니다 . 
 경험 정보 를 보관 할 스택 이 필요 하 죠 . 
 초기 경험 정보 를 생성 하 여 스택 에 보관 하 세요 . 
 스택 이 빌 때 까지 반복 합니다 . 
 스택 에서 경험 정보 를 꺼내 오 세요 . 
 현재 경험 정보 를 출력 하 여 어떻게 진행 하 는지 확인 합시다 . 
 스택 에서 꺼내 온 경험 정보 에서 다음 경험 목록 을 조사 하 세요 . 
 조사 한 다음 경험 목록 을 순차 적 으로 방문 합니다 . 
 만약 목적지 에 도달 하 였으면 원 하 는 솔루션 입니다 . 
 솔루션 의 결과 를 출력 하 세요 . 
 더 이상 필요 없 는 경험 정보 는 소멸 해야 겠 죠 . 
 그렇 지 않 다면 다시 스택 에 보관 하 세요 . 
 더 이상 필요 없 는 경험 정보 는 소멸 하 세요 . 
 다음 은 방향 성 있 는 그래프 에서 실행 한 결과 입니다 . 
 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 
 다음 은 방향 성 없 는 그래프 에서 실행 한 결과 입니다 . 
 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 2 4 6 3 
 Foots : 0 2 4 6 3 1 
 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 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 4 6 3 
 이상 으로 인접 행렬 로 그래프 를 표현 하 고 그래프 에서 경로 를 찾 는 깊이 우선 탐색 알고리즘 구현 을 마칠게요 . 앞 에서 도 얘기 했 듯이 인접 행렬 로 그래프 를 표현 할 때 는 정점 의 개수 가 적 을 때 사용 하 세요 . 정점 의 개수 가 많 아 지 면 필요 없 는 간선 정보 가 기하급수 적 으로 늘어나 성능 에 문제 가 발생 합니다 . 
 이 책 에서 는 바로 이어서 그래프 를 정점 과 간선 의 집합 으로 표현 하 는 방법 을 다룰 거 예요 . 구현 비용 은 인접 행렬 로 구현 하 는 것 보다 많이 들 지만 정점 의 개수 가 많 아 졌 을 때 인접 행렬 로 표현 한 것 보다 성능 이 좋 아 집니다 . 
 Previous Post 10 . 3 . 1 그래프 구현 
 Next Post 10 . 3 . 3 깊이 우선 탐색 ( 인접 행렬 ) 코드 
 532 이 글 :