DFS (Depth-First-Search)은 깊이 우선 탐색 알고리즘의 줄임말입니다.

필요성

  • 한 node에서 목표 node로 도착할 수 있는 경로(short-path)를 찾을 때
  • 예) 미로찾기, 재귀, 백트레킹

구현

구현 방법은 두 가지만 기억하면 됩니다.

  1. 문제를 그래프로 구현한다.
    • 인접 리스트(adjacency list)을 사용해서 이웃 node와의 관계를 기록한다.
      • 장점: 인접 행렬(모든 노드의 관계 저장)보다 효율적인 메모리 사용 (연결된 노드만들 저장하기 때문)
      • 단점: 두 노드가 연결되어있는지 확인하는 속도 느림 (특정 노드와 연결된 모든 인접 노드를 순회해야하기 때문)
        • 이런 속성 덕분에 특정 노드와 연결된 모든 인접 노드를 순회해야하는 문제에서 메모리 효율성을 높일 수 있다.
  2. 깊이 우선 탐색 방법을 사용한다.
    • 스택를 생성하고 스택에 첫 번째 노드 넣기
    • 스택에서 노드 꺼내기
    • 노드의 방문 여부를 조사
      • 목적: 탐색 스택에 같은 노드가 반복해서 추가되어 무한 탐색되는 경우를 방지하기 위함
    • 노드를 방문하지 않았다면 노드를 방문한 것으로 표시하고 자식 노드 탐색 시작
    • 자식 노드 중 방문하지 않은 자식 노드만을 탐색 스택에 추가
    • 탐색 스택에 있는 노드가 없어지거나 답을 찾을 때까지 위의 과정 반복
# Make Graph
n, m, v = map(int, input().split()) # n:node개수, m:edge개수, v:시작 node

graph = [[] for _in range(n)]	# node 개수 만큼 빈 list를 만들어준다.
for _ in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)	# node에 연결된 자식 node를 기록한다.
    graph[n2].append(n1)

def dfs(v):
    stack = deque([v])
    visited = []
    while stack:  # stack에 노드가 없을 때까지
        node = stack.pop()
        if node not in visited:  #방문하지 않은 노드만 방문한다.
          	visited.append(node)	#노드를 방문한 것으로 기록한다.
            for child in sorted(graph[node], reverse=True): # pop은 오른쪽 원소부터 꺼내므로 내림차순 정렬해준다.
                if child not in visited:  # 방문하지 않은 자식 노드를 큐에 추가한다.
                    stack.append(child)
    return visited

재귀함수를 이용하는 방법

​ 참고 서적: 이것이 코딩테스트다 by 나동빈

def dfs(graph, v, visited):
  # 현재 노드를 방문 처리
  visited[v] = True
  # 현재 노드와 연결된 다른 노드를 재귀로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)