Bfs Dfs

c++으로 깊이 우선 탐색을 구현하는 방법과 너비 우선 탐색을 구현하는 방법이 어려워서 정리를 해본다..

 

DFS는 깊이 우선 탐색으로 재귀함수나 스택으로 구현한다.

 

1. 탐색 노드를 스택에 삽입하고 방문 리스트에 표시.

2. 스택 최상단 노드에 인접한 노드중 방문하지 않은 노드가 존재한다면 그 노드를 스택에 넣고 방문한다.

   인접노드를 모두 방문했다면 최상단 노드를 꺼낸다.

3. 2번 과정을 계속 반복한다.

 

** 방문 리스트로 검사를 꼭 해줘야 무한 반복에 빠지지 않는다!!

** 스택은 후입선출의 구조이므로 늦게 들어간 노드가 최상단 노드가 됨을 기억하자!

===============================================================================

Bfs는 너비 우선 탐색으로 시작 노드 인접 노드를 우선으로 확인한다. 큐 자료구조를 이용한다.

주로 특정 조건의 최단 경로를 확인할 때 많이 사용.

 

1. 탐색 시작 노드를 큐에 넣고 방문처리

2. 큐에서 노드를 꺼낸 후 해당 노드 인접 노드 중 방문하지 않는 노드를 모두 큐에 삽입하고 방문 처리해준다.

3. 2의 과정을 계속 반복한다.

 

**큐는 선입 선출의 방식으로 처음 삽입된 노드부터 pop된다!!

 

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

또한 앞 뒤 좌 우로 움직이는 경우에 배열을 이용한다.

dx[]={0,0,1,-1};

dy[]={1,-1,0,0}; 의 배열을 설정해 준 다음

for(int i=0;i<4;i++){

x+dx[i];

y+dy[i];

}

의 형태로 써주면 더 간단하게 움직일 수 있당