[알고리즘] 깊이 우선 탐색(DFS)이란? (개념, 예제, python)

깊이 우선 탐색 (DFS) 이란?

*그래프 탐색

하나의 정점에서 시작하여 모든 정점들은 한 번씩 방문하는 작업

Depth First Search. 현재 탐색하고 있는 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방법.

깊이를 우선적으로 탐색한다.

• 방법
  • 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다.
  • 탐색하지 않은 이웃 노드가 없는 경우, 이전 노드로 돌아간다.
  • 위 작업을 모든 노드를 방문할 때까지 반복한다.
• 그림으로 표현하기
  • 그림

 

예제로 이해하기

예제 1 : 연결 요소의 개수 (백준 11724번)

• 문제
  • 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오.
• 해결 방법
  • 연결되어 있는 영역이 몇 개인지 구하는 문제이다.
  • 방문되지 않은 노드마다 해당 노드와 연결된 모든 노드들을 DFS로 방문한다. (-> 영역1)
  • 다음 노드들을 차례로 확인하며, 방문되지 않은 노드가 있을 경우 영역+1을 추가하고, 위 작업을 반복한다.
• 풀이 코드

import sys
sys.setrecursionlimit(10**6)


def dfs(graph, node, visited):
    visited[node] = True

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)


def solution():
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v = map(int, sys.stdin.readline().split())
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * (N + 1)

    components = 0
    for node in range(1, N + 1):
        if not visited[node]:
            dfs(graph, node, visited)
            components += 1

    print(components)


if __name__ == "__main__":
    # 11724번 : 연결 요소의 개수
    # Level : 실버 2
    # https://www.acmicpc.net/problem/11724
    solution()

 

예제2 : 신기한 소수 (백준 2023번)

• 문제
  • N이 주어진다.
  • N자리 숫자 중에서 '신기한 소수'인 수를 모두 출력해라.
  • 신기한 소수
    • ex. 7331 -> 왼쪽부터 1자리, 2자리, 3자리, 4자리 수가 소수이다. (7, 73, 733, 7331)
• 해결 방법
  • 가능한 모든 수를 확인한다.
  • ex. 7이 소수이면 71, 72, 73, ... 79가 소수인지 확인한다.
    • 소수인 경우 711, 712, ... 를 확인한다. 이를 N자리가 될 때까지 확인한다.
    • (단, 짝수는 소수가 아니므로 제외하고 확인한다.)
• 코드

import sys
import math
sys.setrecursionlimit(10**6)


def is_prime(number):
    '''소수면 True, 아니면 False를 반환한다.'''
    for i in range(2, int(math.sqrt(number))+1):
        if number % i == 0:
            return False
    return True


def dfs(number, length):
    '''dfs 알고리즘으로 탐색한다.'''
    if len(str(number)) == length:
        print(number)
        return

    for i in range(1, 10, 2):
        next_number = number * 10 + i
        if is_prime(next_number):
            dfs(next_number, length)


def solution():
    N = int(sys.stdin.readline())

    # 1자리 숫자는 2,3,5,7이 소수이므로 해당 숫자부터 시작하여 탐색한다.
    dfs(2, N)
    dfs(3, N)
    dfs(5, N)
    dfs(7, N)


if __name__ == "__main__":
    # 2023번 : 신기한 소수
    # Level : 골드 5
    # https://www.acmicpc.net/problem/2023
    solution()

 

 

시간 복잡도

DFS는 그래프/트리를 구현하는 방법에 따라 시간 복잡도가 다르다.

• 인접 행렬
  • 2차원 행렬로 구현하는 경우 각 노드마다 나머지 노드와 연결되어 있는지 확인하기 때문에, O(N^2)의 시간이 소요된다.
  • ex. 노드 a, b가 있을 때 연결되어 있으면 graph[a][b] = True, 연결되어 있지 않으면 graph[a][b] = False로 표현한다.
• 인접 리스트
  • 인접 리스트로 구현하는 경우 각 노드마다 연결되어 있는 노드만 확인하면 되므로, O(N)의 시간이 소요된다.
  • ex. 노드 a와 연결되어 있는 노드는 graph[a] = [b, c, d]로 표현한다.