DFS

DFS정의

깊이 우선 탐색 ( DFS )은 트리 또는 그래프 데이터 구조 를 탐색하거나 검색하기 위한 알고리즘 입니다.

알고리즘은 루트 노드 에서 시작 하여(그래프의 경우 루트 노드로 임의의 노드를 선택) 역추적하기 전에 각 분기를 따라 가능한 한 멀리 깊이 탐색합니다. 추가 메모리는 스택을 이용하며 그래프의 역추적에 도움이 되는 지정된 분기를 따라 지금까지 발견된 노드를 추적하는 데 필요합니다.

한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 가른 방향으로 다시 탐색을 진행합니다.

사용

• MAZE 미로탐색

• CYCLE 순환확인

• Topology 위상정렬(작업스케줄링에서 사용)
  방향 그래프에 대해 정점들의 선행 순서를 위배하지 않으면서 모든 정점를 나열하는 것

그래프 실습

그래프 설명

그래프 탐색 과정 DFS

DFS기본 코드

순환사용(재귀함수)과 스택사용(STACK)으로 DFS를 다양하게 정의할 수 있다.

그래프 : G = { V, E }
정점들의 집합 : V
간선들의 집합 : E
어디로 이동할 수 있는지 : Adj[ ]
잠시 다음으로 이동할 수 있는 노드를 임시로 넣어두는 저장소 : Q(queue형태)
방문했던 노드인지 확인하는 저장소 : visited(list형태로 bool값 이용) 방문하지 않은 경우 : F
방문한 경우 : T

pseudocode

순환을 사용한 DFS

visited[S] = true
for ( i in adj\[S] )
	if( !visited\[i] )
    DFS(i)

c++ code

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

class CGraph {
	int n_vertices;
	bool* visited;
	vector<list<int>> adj; //간선
	vector<int> dist; //정점간 얼마나 떨어져 있는지

public:
	CGraph(int _n) {
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i) {
			visited[i] = false;
		}
		adj.resize(_n);
		dist.resize(_n);
	}
	~CGraph() {
		delete visited;
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}
	//DFS알고리즘 (순환)
	void DFS(int _s) {
		visited[_s] = true; //시작점을 방문한다.
		cout << _s << " ";
        //이터레이터 사용
        //같은 컨테이너에 저장되어 있는 원소를 참조
		list<int>::iterator iter;
		for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter)//이터레이터 사용, 모든 원소를 본다.
			if (!visited[*iter]) //포인터로 표현해주어야 한다.
            	visited[*iter] = true;
				DFS(*iter);
	}
};

iterator

• 반복자 이터레이터는 포인터와 유사하다.
• vector, deque, set, map, list등과 같은 컨테이너에 저장되어 있는 원소를 참조(접근)할 떄 사용된다.
• stack, queue에는 iterator가 없다.
• 선언

vector<int>::iterator i;
list<string>::iterator i;
deque<int>::iterator i;

BFS와 DFS의 차이점

그래프를 탐색하는 2가지 방법인 BFS(Breadth First Search)와 DFS(Depth First Search)의 차이점에 대해서 알아본다.

• 방문의도(목적)에 따른 차이점
  BFS : 모든 노드를 방문하고자 하는 경우
  DFS : 가까운 노드부터 탐색하고자 하는 경우
• 속도에 따른 차이점
  BFS : 자체적인 속도는 DFS보다 빠르다
  DFS : 자체적인 속도는 DFS보다 느리다(코드가 간결함!)
• 데이터 그래프에 따른 차이점
  BFS : 그래프의 규모가 크지 않음, 가중치가 없는 그래프, 최단거리를 구해야하는 경우
  DFS : 그래프의 규모가 큼, 경로의 특징을 저장해두어야 하는 경우
• 구현에 따른 차이점
  BFS : QUEUE자료구조를 이용하여 구현
  DFS : STACK 또는 CYCLE(순환:재귀함수)로 구현

추가

문제소개3

예제 문제 3
1. 수거 로봇을 이용해 쓰레기를 수거합니다.
2. 쓰레기 로봇이 충전할 수 있는 정착장이 2개 이상 있습니다.
3. 쓰레기와 쓰레기, 정착장과 쓰레기 거리는 모두 1KM로 동일합니다.
4. 각 쓰레기가 정착장과 얼마나 떨어져 있는지 구하세요
5. 쓰레기를 수거하고 돌아오기까지 얼마나...한번 충전으로 갈 수 있는...? 최단거리 x2
정착장 : 0, 3
쓰레기 : 정착장을 제외한 모든 노드

v={0,1,2,3,4,5,6,7,8,9}
E={{0,1},{0,2},{1,2},{1,3},{1,4},{2,3},{3,4},{4,5},{4,6},{4,7},{5,7},{5,8},{5,9},{6,7},{7,8}}

문제소개4

예제 문제 4 (DFS)
1. 수거 로봇을 이용해 쓰레기를 수거합니다.
2. 쓰레기 로봇이 충전할 수 있는 정착장이 하나 있습니다. (수정필요)
3. 쓰레기와 쓰레기, 정착장과 쓰레기 거리는 모두 1KM로 동일합니다.
4. 물살로 인해 역방향 운항을 불가합니다.
5. 9번쓰레기를 수거하러 가는 도중 신호가 끊겼습니다. 수거 로봇이 이동하고 있는 모든 경로를 나열하여, 수거 로봇의 위치를 특정하세요.
정착장 : 0
쓰레기 : 정착장을 제외한 모든 노드

화살표있음 (수정 필요-완료)
v={0,1,2,3,4,5,6,7,8,9}
E={(0,1),(0,2),(1,2),(1,3),(1,4}),(2,3),(3,4),(4,5),(4,6),(4,7),(5,9),(6,7),(7,5),(7,8),(8,5)}

문제풀이4

• 녹음해서 (수정 필요)

#include <iostream>
#include <queue>
#include <vector>
#include <list>
using namespace std;

class CGraph {
	int n_vertices;
	bool* visited;
	vector<list<int>> adj; //간선
	vector<int> dist; //정점간 얼마나 떨어져 있는지

public:
	CGraph(int _n) {
		this->n_vertices = _n;
		visited = new bool[_n];
		for (int i = 0; i < _n; ++i) {
			visited[i] = false;
		}
		adj.resize(_n);
		dist.resize(_n);
	}
	~CGraph() {
		delete visited;
	}

	//방향이 없을 때
	void addUndirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
		adj[_d].push_back(_s);
	}
	//방향을 넣어주고 싶을때
	void addEDirectedEdge(int _s, int _d) {
		adj[_s].push_back(_d);
	}

	void DFS(int _s) {
		visited[_s] = true;
		cout << _s << " ";
		list<int>::iterator iter;
		for (iter = adj[_s].begin(); iter != adj[_s].end(); ++iter)//이터레이터 사용, 모든 원소를 본다.
			if (!visited[*iter]) //포인터로 표현해주어야 한다.
				DFS(*iter);
		/*
		visited[*iter] = true;
		dist[*iter] = dist[_s] + 1; //거리 +1 적용추가
		*/
	}
};

int main() {
	CGraph OGraph(10);
    //방향을 가지는 간선 수정했음
	OGraph.addDirectedEdge(0, 1);
	OGraph.addDirectedEdge(0, 2);
	OGraph.addDirectedEdge(1, 2);
	OGraph.addDirectedEdge(1, 3);
	OGraph.addDirectedEdge(1, 4);
	OGraph.addDirectedEdge(2, 3);
	OGraph.addDirectedEdge(3, 4);
	OGraph.addDirectedEdge(4, 5);
	OGraph.addDirectedEdge(4, 6);
	OGraph.addDirectedEdge(4, 7);
	OGraph.addDirectedEdge(5, 9);
	OGraph.addDirectedEdge(6, 7);
	OGraph.addDirectedEdge(7, 5);
	OGraph.addDirectedEdge(7, 8);
	OGraph.addDirectedEdge(8, 5);

	return 0;
}

BFS

하단의 주소를 눌러서 BFS(+ BFS/BFS문제)를 확인할 수 있습니다.
https://velog.io/@ehekaanldk/BFS