DFS(깊이우선탐색) python으로 구현

Depth First Search, DFS

오늘은 DFS를 알아보자

DFS는 트리나 그래프를 방문 또는 탐색할때 깊이를 우선으로 하는 알고리즘이다.

 

탐색 방법

 

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김

 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행

 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

 4.스택이 빌때까지 2번을 반복

 

시간복잡도는 O(N)

BFS과정에서 큐 대신 스택을 쓰면 DFS!

dfs와 bfs 탐색 과정

 그림을 보면, DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어 있는 모든 길을 넓게 탐색하는 것을 볼 수 있다.

코드 구현

 

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김

 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행

 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

 4.스택이 빌때까지 2번을 반복

 

dfs(그래프 탐색) -재귀

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    # 탐색 순서 출력
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

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

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

dfs(graph, 1, visited)

 

 

dfs(그래프 탐색) - 스택

def dfs_stack(graph, start, visited):
    # 스택 구현을 위한 리스트 사용
    stack = [start]
    
    # 현재 노드를 방문 처리
    visited[start] = True
    
    while stack:
        # 스택에서 가장 최근에 삽입된 노드를 꺼내기
        v = stack.pop()
        # 탐색 순서 출력
        print(v, end=' ')
        
        # 현재 노드와 연결된 노드들을 스택에 삽입
        # 이때 방문하지 않은 노드들만 삽입
        for i in reversed(graph[v]):
            if not visited[i]:
                stack.append(i)
                visited[i] = True

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

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

dfs_stack(graph, 1, visited)

 

 

dfs(2차원 배열)

def dfs_stack(graph, visited):
    # 상하좌우 네 방향을 의미
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    # 스택 구현을 위한 리스트 사용
    stack = [(0, 0)]
    # 현재 노드를 방문 처리
    visited[0][0] = True
    
    while stack:
        # 스택에서 가장 최근에 삽입된 노드를 꺼내기
        x, y = stack.pop()
        # 탐색 순서 출력
        print(x, y, end=' ')
        
        # 현재 노드와 연결된 노드들을 스택에 삽입
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]):
                if not visited[nx][ny] and graph[nx][ny] == 'O':
                    visited[nx][ny] = True  # 방문 표시
                    stack.append((nx, ny))

graph = [
        ['O', 'O', 'O', 'O', 'O', 'X'],
        ['O', 'O', 'O', 'O', 'X', 'O'],
        ['O', 'O', 'O', 'X', 'O', 'O'],
        ['O', 'O', 'X', 'O', 'O', 'O'],
        ['X', 'O', 'O', 'O', 'O', 'O'],
    ]

# 노드별 방문 정보
visited = [[False] * len(graph[0]) for _ in range(len(graph))]

dfs_stack(graph, visited)