DFS 깊이 우선 탐색

froajnzd·2024년 1월 20일

algorithm

목록 보기

6/11

DFS (Depth First Search)
깊이 우선 탐색
하나의 정점에서 시작하여 차례대로 연결된 모든 정점들을 한 번씩 방문하는 방법

DFS의 특징

재귀적으로 동작한다

순환 알고리즘의 형태이다

시간복잡도
인접 행렬 : $O(N^2)$ ➡ V개의 노드에 대해 V개의 엣지 탐색
인접 그래프 : $O(N+E)$ ➡ V개의 노드와 E개의 간선 탐색

📕 DFS를 사용해야하는 문제의 조건

트리 혹은 그래프 탐색 문제여야 한다.
모든 노드를 방문하고자 하는 경우에 사용한다.

💡 DFS의 장점

BFS보다 좀 더 간단하게 구현된다.
현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
그래프에서 순환을 감지할 수 있다.

🥺 DFS의 단점

단순 검색 속도 자체로 BFS에 비해 느리다.
순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
해에 도달하고 탐색을 끝내는 경우, 얻어진 해가 최단 경로라는 보장이 없다.

📝 DFS를 사용하는 문제의 예

한 가지 정점과 연결된 모든 정점을 탐색해야 하는 경우
경로를 찾아야 하는 경우
사이클이 존재하는 경로를 찾는 경우 (이미 방문한 노드를 다시 방문하지 않아야 할 경우)

🎡 DFS를 응용하여 푸는 다른 알고리즘

Binary Tree Traversal
: 전위순회(Pre-order Traversals) / 중위순회(In-order Traversals) / 후위순회(Post-order Traversals)
Topological sort
: DAG = Directed Acyclic Graph ➡ 방향이 있고 싸이클이 존재하지 않는 그래프여야함
Finding connected component (undirected)
: BFS,DFS 모두 가능
Finding Strongly connected component (directed)
: 그래프의 Component 단위는 DAG이다
Critical Path Analysis
: start vertex부터 end vertex까지의 path 중 weight가 가장 큰 path를 찾는 문제
Biconnected Components (Articulation point)

🎁 구현 방법

두 가지 방법으로 DFS를 구현할 수 있다.
1. 재귀(자기 자신을 호출)
2. Stack

🏃‍ 예시 문제 1

<BAEKJOON: 실버 1> 안전 영역

해답

resursion limit를 설정하는 이유 => python은 기본 recursion limit이 1000으로 얕기 때문에 코딩테스트의 테스트 케이스가 1000을 넘어서면 RuntimeError가 발생한다. (코드를 바르게 작성했지만 리밋때문에 틀리는 경우가 발생 할 수 있음) 결국 리밋을 높여준다!!

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

minh, maxh = sys.maxsize, 0

N = int(input())
area = []
for i in range(N):
    area.append(list(map(int, input().strip().split())))
    minh = min(minh, min(area[i]))
    maxh = max(maxh, max(area[i]))

# (i, j)를 포함한 안전지역 방문하기
dx = [0,0,-1,1]
dy = [-1,1,0,0]
def find_safe_area(i, j, rain):
    visited[i][j] = 1
    for p in range(4):
        di = i+dx[p]
        dj = j+dy[p]
        if 0 <= di < N and 0 <= dj < N \
                and not visited[di][dj] \
                and area[di][dj] > rain:
            find_safe_area(di, dj, rain)

# 비의 양(minh~maxh)에 따른 안전지대 수 중 가장 안전지대 수가 많은 값을 찾기
result = 1
for rain in range(minh, maxh):
    visited = [[0] * N for _ in range(N)]
    num_of_safe = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and area[i][j] > rain:
                find_safe_area(i, j, rain)
                num_of_safe += 1
    result = max(num_of_safe, result)

print(result)