[나동빈 코딩테스트] DFS 구현하기 (재귀함수 사용)

### DFS(깊이 우선 탐색) 함수 구현하기 (5줄짜리 코드)

 

def dfs(graph, v, visited):  #그래프의 인접리스트, 시작점, visited 리스트 순

  visited[v] = True  #방문 표시 후 해당 위치 출력
  print(v, end=" ")

  for k in graph[v]:  #해당 노드의 인접노드들 하나씩 체크
    if not visited[k]:  #방문을 안했다면 dfs 함수를 재귀적으로 적용
      dfs(graph,k,visited)
      
# 사용 예시 :: 먼저 인접 리스트를 정의하고 visited 리스트를 만든후에 dfs 함수에 대입.

graph = [ #인접 리스트
  [], #편의상 0인 노드 있다고 가정
  [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) # 탐색하면서 순차적으로 출력

 

#시간 복잡도 : O(N)