DFS

1. 시작 노드를 방문하고, 방문한 노드를 '방문한 노드' 리스트에 추가합니다.
2. 시작 노드와 연결된 다음 노드 중에서 아직 방문하지 않은 노드를 하나 선택합니다.
3. 선택한 노드를 현재 노드로 하고, 해당 노드를 '방문한 노드' 리스트에 추가합니다.
4. 선택한 노드와 연결된 다음 노드 중에서 아직 방문하지 않은 노드를 하나 선택합니다.
5. 이러한 과정을드가 없을 때까지 반복합니다.

 

ex.

    A

   / \

  B C

 / \

D E

 

DFS로 탐색)시작 노드를 A로 선택하고, 이어서 B, D, E, C 순서대로 방문

 

실전)

# 그래프 정의
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': [],
    'D': [],
    'E': []
}

# 시작 노드 설정
start_node = 'A'

# 그래프, 시작노드를 넣으면 탐색 노드들을 뱉는 알고리즘
def dfs(graph, start, visited=None):
	if visited is None:
    	visited = set()
    visited.add(start)
    print(start) # 현재 방문 노드 출력
    
    for neighbor in graph[start]:
    	if neighbor not in visited:
        dfs(graph, neighbor, visited)

print("DFS 탐색 결과:")
dfs(graph, start_node)

 

- usage

1. 그래프 탐색: 그래프 내의 모든 노드를 방문해야 할 때 사용됩니다. DFS는 한 노드에서 시작하여 깊이를 우선으로 탐색하기 때문에 특정 경로를 탐색하거나 순회할 때 유용합니다.
2. 경로 찾기: 두 노드 간의 경로가 있는지 확인할 때 사용됩니다. 시작 노드에서 목표 노드로 가는 경로를 찾는 것이 목적일 때 DFS가 유용합니다.
3. 사이클 찾기: 그래프 내에서 순환 구조를 찾을 때 사용됩니다. DFS는 그래프를 탐색하면서 한 번 방문한 노드를 다시 방문하게 되면 순환 구조가 있는 것으로 간주할 수 있습니다.
4. 위상 정렬: 방향 그래프에서 노드들을 순서대로 나열하는 작업에 사용됩니다. DFS를 통해 그래프를 탐색하면서 역방향으로 노드를 방문하는 순서를 기록할 수 있습니다.
5. 그래프 컴포넌트 찾기: 그래프가 여러 개의 연결된 부분 그래프로 이루어진 경우, DFS를 사용하여 각 컴포넌트를 찾을 수 있습니다.
6. 백트래킹: 백트래킹 알고리즘에서 DFS는 가능한 모든 경로를 탐색하고 해를 찾는 데 사용됩니다.

 

 

- 재귀함수

1. Base case(기본 경우): 재귀 호출을 멈추는 조건입니다. 이 조건이 충족되면 더 이상 함수를 재귀적으로 호출하지 않고 반환합니다.
2. Recursive case(재귀적 경우): 함수가 자기 자신을 호출하는 부분입니다. 이 부분에서는 문제를 더 작은 입력으로 분해하여 재귀적으로 해결합니다.

 

실전)

def factorial(n):
    # Base case: n이 1 이하일 때
    if n <= 1:
        return 1
    # Recursive case: n! = n * (n-1)!
    else:
        return n * factorial(n-1)

# 팩토리얼 계산
result = factorial(5)
print("5! =", result)