[AIGORITHM THEORY] DFS (Depth First Search) 개념정리

이또삐(이민혁)·2023년 4월 20일

Algorithm_Theory

ALGORITHM_THEORY

목록 보기

4/11

개념

그래프 탐색

하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산
많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.
- 예 : 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부

특징

갈 수 있는곳 까지 계속 진행, 더 진행할 수 없으면 돌아온뒤 다시 탐색
stack을 활용
사용하고자 하는 의도에 따라 전위 순회(Pre-order), 중위 순회(Inorder), 후위 순위(Post-order)로 나뉠 수 있다.
DFS의 대표적인 순회 방식은 전위 순회(Pre-orfer Traverse)이다.

원리

하나의 정점 방문
이웃한 정점으로 갈 수 있으면 무조건 이웃 중 하나로 방문
- 과거에 방문하지 않은 정점이어야 함
(1)-(2)를 반복
- 시작점에서 점점 깊이 깊어지는 노드로 전진하게 됨
만약 방문 가능한 이웃 정점이 없다면 왔던 경로 상의 가장 최근에 방문했던 (most recently visited) 정점으로 돌아가서 (backtracking) 그 정점의 이웃 노드 방문을 시도 → 스택 이용

알고리즘

시작 정점 v를 결정하여 방문
정점 v에 인접하고 아직 방문하지 않은 한 정점 w 선택
- 방문하지 않은 정점 w가 없다면 (3) 로 감
- 방문하지 않은 정점 w가 있다면
  1) 정점 v를 스택에 push, pred(w) = v라 셋팅
  2) w를 v로 하여 (1)로 감
스택에서 pop
- 공백이라면 알고리즘 종료
- 공백이 아니라면 꺼낸 정점을 v로 하여 (2)로 감

vs BFS

장점

DFS는 각 Level에 일부분만 저장 하므로 BFS에 비해 메모리 메모리 사용률이 적다.
찾고자하는 답이 트리에서 부터 멀어질 수록 DFS가 유리하다.

단점

해가 없는 경로를 탐색할 경우 단계가 끝날때까지 탐색. 효율성을 높이기 위해 미리 지정한 깊이까지만 탐색하도록 하는것이 좋다.
dfs를 통해 얻어진 결과가 최단경로라는 보장은 없다. dfs는 해당 경로에 도착하면 탐색을 종료하기 때문

시간복잡도

인접 행렬로 표현한 경우 시간 복잡도
• O(n^2)
인접 리스트로 표현한 경우 시간 복잡도
• O(n+e)

필기

DFS , BFS 모두 방문기록을 활용하는 방식이다. → visit(), visit[i][j] 방문 기록을 남기는 방향으로 문제를 푸는 유형이다.
DFS에 조건을 거는데, break은 특이사항이 아니라면 거의 없다. (대부분 countinue를 사용
if문이 끝나면 재귀문은 알아서 끝난다.
dfs의 큰 틀은 항상 똑같다. 여차하면 외우는게 좋을지도 모른다.
- n x m 행렬문제는 dy, dx를 활용해 다음위치를 생각한다 항상.
dfs의 유형은 크게 3가지로 나눌 수 있다.
1. 한가지 정점과 연결된 모든 정점을 탐색해야 하는 경우
  
  일반적인 dfs알고리즘을 사용하면된다. 해당 지점 방문 여부를 체크할 배열(visit)을 선언하고, 그 정점과 인접한 정점중 아직 방문하지 않은 곳을 재귀호출하는 방식으로 풀이가 가능하다.
2. 경로를 찾아야 하는 경우
  
  일반적인 방법이 아니기 떄문에, dfs알고리즘을 약간 변형해야한다.
3. 사이클이 존재하는 경로를 찾는 경우
  이전에 방문했던곳을 다시 방문하는 원형 반복 사이클이 생겼다는것을 의미하는데, 일반적인 dfs는 방문한곳을 다시 방문하지 않기 떄문에, 기존 알고리즘에 변형을 주어 문제를 해결해야 한다.
  관련 문제 - https://www.acmicpc.net/problem/9466

코드

수도코드

dfs(G, v)
visit(v)
visited[v] ← true
for all w ∈ (v 인접 정점) do
if w가 아직 방문되지 않았으면 then
pred[w] ← v
dfs(G, w)
end dfs()

def dfs(graph, v, visited, pred):
global result
# 현재 정점을 방문 처리
visited[v] = True
result.append(v)
# 현재 정점의 인접 정점을 재귀적으로 방문
for i in range(7):
if graph[v][i] and (not visited[i]):
pred[i] = v
dfs(graph, i, visited, pred)

백준 1260 풀이

from collections import deque
# n: 정점의 개수, m: 간선의 개수, v:탐색을 시작할 정점의 번호
n, m, v = map(int,input().split())
 
graph = [[] for _ in range(n+1)]
 
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
 
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for j in graph[v]:
        if not visited[j]:
            dfs(graph, j, visited)

visited = [False] * (n+1)        
dfs(graph, v, visited)