DFS

Depth First Search

깊이 우선 탐색

그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가 노드를 방문한 뒤, 다시 돌아가 다른 경로로 탐색하는 알고리즘

다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법

BFS 보단 느리다 (단순 검색 속도)

백트래킹과 연관된다

 

DFS를 사용하는 경우

모든 노드를 방문하고자 할 때

순회를 하고자 할 때

경로에 특징을 저장해야 할 때

검색 대상 그래프가 클 때

cf) 최단거리는 BFS가 유리

 

동작 방식

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 2번을 더 이상 수행할 수 없을 때 까지 반복

방문 처리

 

스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않도록 체크하는것

방문처리로 인해 각 노드를 한 번씩만 처리할 수 있다

 

시간 복잡도

 

O(N), N: 데이터의 개수

 

code

def dfs(graph, v, visited):
    visited[v] = True # 방문 처리 
    print(v, end=' ') # 방문 노드 출력 
    for i in graph[v]: # 인접 노드 방문 
        if not visited[i] # 방문 한 적이 없으면 
            dfs(graph, i, visited) # dfs 호출 

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visitd = [False] * 9

dfs(graph, 1, visited)

예제

1260번: DFS와 BFS

1260번: DFS와 BFS

2178번: 미로 탐색

2178번: 미로 탐색