DFS 알고리즘

안녕하세요? 오늘은 기초 알고리즘 중 하나인 DFS(깊이 우선 탐색)을 알아보도록

하겠습니다. dfs는 백트래킹의 사용되는 알고리즘으로 스택(리스트)를 필수적으로

사용해야 합니다.

 

dfs는 한마디로 루트노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.

쉽게 말하면 미로 찾기를 할 때 한 방향으로만 가다가 벽이 나오면 이전에 있는 갈림길 중 가장 가까운 갈림길로

다시 돌아가는 것을 의미합니다.

 

탐색 순서

 

다음은 예시 코드입니다.

 

step 1 : 함수 정의

def dfs(now): # 함수정의. now = 현재 정점
    print(now,end=' ') #현재 정점 프린트
    visited[now] = 1 # 무한 루프 돌지 않게 방문 채크
    for i in l[now]: #now와 연결된 정점 꺼내기
        if visited[i] == 0: #만약 이미 방문하지 않았다면
		dfs(i) #재귀
    return # 함수 종료

 

step 2 : 입력 및 기본 세팅

n = int(input()) # 정점 개수 입력
visited = [0 for _ in range(n+1)] # 채킹 배열 초기화
l = [[] for _ in range(n+1)] # 입력 받을 리스트
for i in range(n-1): # 트리의 성질 : 정점의 수 - 1 = 간선의 수
    a,b = map(int, input()) #연결 되어 있는 두 정점 입력
    l[a].append(b) # 입력 리스트에 서로 연결 시키기
    l[b].append(a)
 dfs(1) # 1번 정점부터 탐색