[알고리즘] 길찾기 알고리즘 #1- 길찾기가 가능한지?/BFS / C++

이전에 작성하였던 넓이우선탐색(BFS)은 말그대로 해당 그래프에 어떤 요소가 있는지 전체적으로 탐색한것이였다.

 

이제 여기서 좀 더 나아가 해당 그래프에서 시작점과 목표점를 정하여 해당 두 점이 이어져 있는지 확인하는 알고리즘을 확인해보자 .

 

이전에 사용했던 큐, 노드 클래스는 그대로 사용 (큐의 함수 이름은 보통의 STL의 큐와 같이 바꿨다)  

 

이전에 작성했던 Graph 클래스에서 새롭게 추가 된 bool형을 반환하는 Search함수이다.

 

이제 이 함수를 이용해서 확인해보자.

 

이런 그래프가 있다고 하면

 

6과7이 나머지 노드들과 떨어져 있는 상태이다.

예를 들어 1에서 7까지 갈수 있는지 여부를 확인한다고 하면 

 

 

결과가 0이 나온다(실패)

 

이제 이 노드들을 이어준다.

 

이렇게 5번과 6번 노드를 추가로 이어주고,

 

AddEdget(5,6)을 추가해준 뒤 확인해보면 

 

결과는 1로 출력된다.(성공)

 

 

여기까지는 이제 갈수 있는지 없는지 여부만 확인 했다면

 

 

하지만, 여기서의 단점은 목표지점이 나올때까지 모든 지점의 노드들을 다 검사한다는 것이다.