문서 보기문서 편집수정 내역 깊이 우선 탐색 (덤프버전으로 되돌리기) [include(틀:다른 뜻1, other1=신용카드 회사 Discover Financial Service, rd1=디스커버)] [include(틀:이론 컴퓨터 과학)] [목차] == 개요 == {{{+2 Depth First Search, DFS}}} 그래프 순회 방식의 일종. 거의 항상 [[너비 우선 탐색|너비우선탐색(BFS; Breadth First Search)]]과 비교되어 나온다. == 상세 == [[트리(그래프)|트리]]나 [[그래프]]에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 [[백트래킹]]에 사용한다. 일반적으로 [[재귀함수|재귀호출]]을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 [[버퍼 오버플로|스택 오버플로우]]를 유의해야 한다.[* 쉽게 말하자면, [[메모리]] 구조 스택의 한계 메모리를 초과하는 것이다.] 갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료. 단순 검색 속도 자체는 [[BFS]]에 비해서 느리다. 하지만 검색이 아닌 순회(traversal)를 할 경우는 많이 쓰인다. DFS는 특히 리프 노드에만 데이터를 저장하는 정렬 트리 구조에서 항상 순서대로 데이터를 방문한다는 장점이 있다. [[백트래킹]]에 사용되는 이유도 공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내버리는게 가능하기 때문이다. 자동 [[미로]] 생성에 많이 사용되는 [[알고리즘]]이기도 하다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫으면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생긴다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생긴다. 직접 보고 싶다면 [[http://youtu.be/0kaHIfrB3T4|이 동영상]]을 보자. 유향그래프에서 [[그래프(이산수학)#s-2.2.2|사이클]]이 있는지 판단하는 것도 가능하다. 즉, 어떤 한 노드에서 간선을 따라 방문하다 보면 자기 자신으로 돌아올 수 있는 경로가 있는지 확인할 수 있다. == 장단점 == === 장점 === * 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. * 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. === 단점 === * 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다. * 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다. == 소스 코드 == === C++ === {{{#!syntax cpp const int MAX = 100'001; bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다. void dfs(const vector graph[], int current) { // graph는 인접 리스트, current는 현재 노드 visited[current] = true; // current 방문 for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자. if(!visited[next]) { // 만일 next에 방문하지 않았다면 dfs(graph, next); // next 방문 } } } }}} === Python === {{{#!syntax python def dfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다. visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다. def search(current:int): # 재귀함수 정의 visited[current] = True # current 방문 for nxt in graph[current]: # current의 인접 노드를 확인한다. 이 노드를 nxt라고 하자. if not visited[nxt]: # 만일 nxt에 방문하지 않았다면 search(nxt) #nxt 방문 search(start) }}} == DFS [[트리(그래프)|트리]] == 한 정점을 두 번 이상 방문하지 않는 연결그래프에서 DFS 트리라는 유향트리 구조가 만들어진다. * Tree edge란 DFS중 a정점을 방문한 후 b정점을 처음 방문할 때, a→b의 유향간선을 말한다. * Back edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, b가 a의 조상일 때 a→b의 유향간선을 말한다, * Forward edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a가 b의 조상일 때 a→b의 유향간선을 말한다. * Cross edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a→b의 유향간선이 Back edge나 Forward edge가 아닌 경우를 말한다. DFS 트리를 사용하면 unrooted tree를 rooted tree로 만들 수 있다. 이 경우에는 Tree edge 이외의 간선이 존재하지 않게 된다. [[분류:탐색 알고리즘]]캡챠되돌리기