깊이 우선 탐색

Depth-First Search, DFS

개요

갈림길에서 한쪽 끝까지 탐색하고, 더이상 탐색할 수 있는 곳이 없다면 돌아와서 다른 길을 탐색하는 방식입니다.

구현

재귀 함수를 이용해 구현합니다.

def dfs(adj, visited, current):
    visited[current] = True
 
    for next_ in adj[current]:
        if visited[next_]:
            continue
 
        dfs(adj, visited, next_)

문제

• 2606번: 바이러스 풀이
• 1012번: 유기농 배추 풀이
• 11724번: 연결 요소의 개수
  임의의 두 정점 에서 로 가는 경로가 존재하면 연결 그래프라고 합니다.
  연결 그래프가 아닌 그래프는 연결 그래프들의 집합으로 볼 수 있으며, 이때 각각의 연결 그래프를 연결 요소라 부릅니다.