[파이썬] 탐색 알고리즘 정리 - 깊이 우선 탐색(DFS) (python)

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

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 갈 수 있는 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문하는 방법

특징

• 가장 마지막에 만났던 정점으로 돌아가 다시 탐색을 반복하므로 LIFO 구조의 스택 사용
• 넓게 탐색하기 전에 깊게 탐색하므로 깊이 우선 탐색(DFS)
• 깊이 우선 탐색(DFS)이 넓이 우선 탐색(BFS)보다 간단
• 탐색 속도는 DFS가 BFS보다 느림
• 스택과 재귀 알고리즘의 형태로 구현 가능
• 트리에서 사용되는 모든 순회는 DFS 의 종류

DFS의 탐색 과정

출처 : https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

BFS와 다르게 그래프의  깊이를 따라 방문하는 특징을 갖고 있다.

주로 이럴 때 사용

• 미로 탐색 문제 등의 알고리즘
• 경로의 특징을 저장해야하는 문제
• 검색 대상 그래프가 많을 때 최단 거리를 찾는 문제(적을 땐 BFS를 더 활용됨)

그래프 탐색 활용 코드(위 그림 예시)

# 재귀를 활용
def dfs(n): # dfs 정의
    visited[n] = True
    print(n, end=' ')
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

graph = [[],[2,5,9],[3],[4],[],[6,8],[7],[],[],[10],[]] 
visited = [False] * 11 #방먼처리를 위해 생성(dfs는 재귀로 동작하니 꼭 함수 밖에 작성)
dfs(1)한 DFS 코드

#출력 : 1 2 3 4 5 6 7 8 9 10

---

반응형

#시작 지점이 2, 종점이 3인 미로를 종점까지 갈 수 있는지 탐색하는 코드 (stack 활용)
def dfs(a, b):
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 상하좌우
    stack = [[a,b]] # 스택 지정
    while stack:
        y, x = stack.pop()
        if maze[y][x] == 3:
            return 1  # 도착시 1 반환
        maze[y][x] = 1
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            # 범위 밖을 벗어나지 않으면서 1이 아니고, 방문하지 않았을 경우
            if 0 <= ny < N and 0 <= nx < N and maze[ny][nx] != 1 :
                stack.append([ny, nx])
    return 0

N = 5
maze = [[1,1,1,2,1],[1,1,1,0,1],[1,1,1,0,1],[1,1,1,0,1],[1,1,1,0,3]]
print(dfs(0,3))

#출력 1

 

개인 의견

탐색 문제를 해결할 때 가장 많이 사용되는 기술인 DFS

백트레킹을 이용한 문제 해결에도 사용하는데, 백트레킹과 DFS는 많이 유사한 기술이지만 조금 다르므로 나중에 따로 정리할 예정이다. 😀