이호진
탐색 알고리즘 DFS (2021/02/21) 본문
DFS란 깊이 우선 탐색을 말한다.
탐색 시작 노드를 스택에 삽입하고 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
스택에 넣고 방문처리 스택에 넣고 방문처리 이 반복을 재귀함수를 이용하여 진행한다.
예제를 풀어보면,
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] 이렇게 나타낸 그래프가 있을 때 (통상적으로 1부터 시작하므로 0번을 비워놓는다.)
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,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
dfs(graph,1,visited)
dfs 함수부터 살펴보면 graph와 v(탐색시작노드) visited(방문처리 여부)를 입력받는다.
visited[v]=True로 탐색시작노드를 방문처리하고 값을 출력한다.
입력받은 그래프를 차례로 탐색하면서 방문하지 않은 노드에 대해 다시 dfs함수를 이용해 처리한다.
아래 메인함수에서는 그래프의 값을 입력하고 visited를 전부 False처리해준다. 숫자는 총 8개이지만 그래프에서 0번째를 비워두었기 때문에 9를 입력한다. 그리고 dfs함수를 이용하여 1부터 탐색한다.
결과로는
1 2 7 6 8 3 4 5
이 출력된다.
DFS에서는 스택과 재귀함수를 이용한다.
'주요 알고리즘' 카테고리의 다른 글
음료수 얼려먹기 - DFS (2021/02/22) (0) | 2021.02.22 |
---|---|
탐색 알고리즘 BFS (2021/02/21) (0) | 2021.02.21 |
문자, 숫자 재정렬하기 (2021/02/19) (0) | 2021.02.19 |
시각 - 완전탐색 (2021/02/19) (0) | 2021.02.19 |
상하좌우 - 벡터 구현문제 (2021/02/18) (0) | 2021.02.18 |