2021.11.13 코테_DFS 예시코드

2021.11.13 코테_DFS 예시코드

728x90

# 오늘의 문제

DFS ( Depth-First Search) 예시코드

# DFS

너비우선 탐색 - 그래프 ( 간선과 노드로 이루어진) 라는 자료구조를 탐색하는 문제가 많이 출제된다. 거기에서 사용하는 알고리즘이라고 표현할 수 있겠다.

아래의 코드는 해당 그래프를 DFS로 탐색하는 방법의 예시를 코드로 옮겨 놓은 것이고 이로써 직접 작성해보며 DFS에 대한 이해를 높이기 위해 서술 해두었다.

#DFS 예제 #노드 구조를 그래프로 하고 #v 가 노드이름 #visited가 방문해본 곳 true false def dfs(graph, v, visited): visited[v] = True print(v, end=' ') #v의 리스트 안의 i들중 방문 안해봤으면 재귀함수 세팅 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)

728x90

from http://meotlog.tistory.com/44 by ccl(A) rewrite - 2021-11-13 19:26:38