DFS(Depth-First search)
탐색 알고리즘의 일종이다. 그래프로 데이터가 주어졌을 때, 시작 노드에서 가장 먼 곳(깊은 곳)까지 탐색하며, 더 이상 갈 수 없을 때까지 탐색한다.
보통 모든 노드를 탐색해야 할 경우 이 알고리즘을 사용하곤 한다.
구현
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함
2. 스택의 최 상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
흐름을 이해하는데 도움을 주었던 위키피디아 gif를 첨부한다.
링크텍스트
스택의 선입후출 방식은 프로그래밍에서 재귀함수가 호출되는 방식이기도 하며, 재귀함수로 스택 관련된 알고리즘을 구현하면, 코드가 단순해지고, 이해하기 쉬운 부분이 있으므로, 필자는 구현하는데에 재귀함수를 사용하였다.
def dfs(graph, v, visited): #v = 현재 탐색 노드
visited[v] = True #현재 노드를 방문 처리
print(v, end=' ')
for i in graph[v]: #현재 노드와 연결된 다른 노드를 재귀적으로 방문
if not visited[i]:
dfs(graph, i,visited)방문 처리를 체크하는데에, bool타입의 visited[]를 생성하였다.
visited=[False]*11 #노드의 개수 +1개의 bool타입 리스트 생성
#방문 여부를 체크하기 위함
graph = [
[], #왜 공란인지 밑에서 설명
[2,5,9],
[1,3,4],
[2,4],
[3],
[1,6,8],
[5,7],
[6],
[5],
[1,10],
[9]
]
dfs(graph,1,visited)첨부한 gif를 python으로 구현한 main문이다.
필자는 graph를 구현하는데 2차원 리스트를 사용하였다. 파이썬의 경우 딕셔너리로도 구현이 가능하다.
graph[0]을 비워둔 이유에 대해 설명하자면, 보통 노드를 0번 노드부터 탐색한다, 혹은 노드가 10개가 있다고 가정할 때 0,1,2,3,4,5,6,7,8,9 이런 식으로 세는 사람은 없을 것이다.
하지만 리스트, 혹은 다른 언어에서 배열 같은 경우 인덱스는 0부터 시작하고, 길이가 10인 리스트를 만들면 9번 인덱스가 마지막 인덱스라는 것은 다들 잘 알고 있을 것이다.
따라서, 편의를 위하여 0번 인덱스를 비워두고, 1번 인덱스를 1번 노드라고 가정하고, 탐색을 시작하기 위함이다.
1 2 3 4 5 6 7 8 9 10위의 코드를 실행하면 다음과 같은 결과가 나오고, 첨부한 gif를 같이 보면, 이해하는데 도움이 될 것이다.
