DFS

* 해당 포스트는 코드트리를 활용한 포스팅입니다.

 

DFS (Depth First Search, 깊이 우선 탐색)

: 최대한 깊게 탐색한 후 더 이상 도달할 수 없는 상황이라면, 다시 이전으로 돌아간다. 

특징 

1. 특정 지점을 방문하고, 이후에 주변 노드를 탐색한다. 

 

2. DFS는 재귀를 활용해 구현하는 경우가 많다.

 

 ex) 방문할 수 잇는 지점이 있다면,

• 그 지점을 방문하는 함수를 재귀적으로 호출
• 없다면 함수를 종료

3. 이미 방문했던 지점을 또 방문하면 효율이 떨어진다. 

    이전에 방문했던 지점은 다시 방문 x => '처리'를 해야함 

    => 처리 : visited란 배열을 만들어서, 번호를 갖고 있는 지점을 방문한 적이 있는지 확인하며 진행하기 

DFS STACK 진행 과정 

4. 그래프의 정점이 100개라면, DFS를 수행하는 동안 재귀함수의 깊이(콜 스택에 들어가는 함수의 수)는 50을 초과할 수도 있다.

 

def dfs(pos):
	visit(pos)
    for children of pos
    	if visited[child] == false
        	dfs(child)

연결 요소가 여러 개 있는 경우 

1. 1번 정점으로 DFS 시작

2. 방문하지 않은 정점 중 번호가 가장 낮은 지점을 시작으로 다시 탐색 (8번, 9번 순서대로 탐색 진행)

 

---

DFS 예제 문제

https://www.codetree.ai/missions/6/problems/dfs-graph/description

코드트리 - DFS/도시 방문

 노드의 번호가 작은 것 부터 먼저 탐색한다고 정할 때, 방문 순서를 적어봅시다.

 

1번 - 3번 - 2번 - 6번 - 5번 - 4번 

 

1번이 갈 수 있는 경로 : 3번, 4번 (우선순위로 3번)

3번이 갈 수 있는 경로 : 2번, 4번, 5번 (우선순위로 2번)

2번이 갈 수 있는 경로 : 3번, 6번 (3번은 이미 갔던 곳)

6번이 갈 수 있는 경로 : 2번, 5번 (2번은 이미 갔던 곳

5번이 갈 수 있는 경로 : 3번, 6번(둘다 갔던 곳이므로 이전 정점으로 돌아감)

6-2번을 거침 

3번이 갈 수 있는 경로 : 2번 , 4번, 5번 (다 이미 갔던 곳으로 마지막 4번)

 

---