2021.11.13 코테_DFS 예시코드

# 오늘의 문제

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)