"""
p,137 ~ p, 142
5-8.py DFS 예제
# 탐색 알고리즘 - 깊이우선탐색 DFS
- '[ 가장 깊숙이 위치하는 노드에 닿을 때 ]'까지 확인(탐색) 하면 된다. 
# 1. 탐색 시작 노드를 [ 스택에 삽입 ]하고 방문 처리를 한다.
# 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 
     그 인접 노드를 스택에 넣고 방문 처리를 한다. 
    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
# 3. [ 2번의 과정을 더 이상 수행할 수 없을 때까지 ] 반복한다.
"""
# 책 정답 
# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 [ 방문 처리 ]
    visited[v] = True
    print(v, end=' ') # 출력하고 한칸 공백을 둬라 .
    
    # [ 현재 노드와 연결된 ] 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: # 만약에 방문하지 않았을경우 재귀 호출. 
            dfs(graph, i, visited)

# [ 각 노드가 연결된 정보를 ] 리스트 자료형으로 표현(2차원 리스트)
'''
# 보통 0부터가 아닌 [ 노드의 번호가 1부터 ] 출발한다고 치면
  [ 첫번째 인덱스는 ] 비워둔다. 
  0인덱스는 무시해버리고 '1 부터 채우는 방식'을 더많이 사용한다.
# [ 이게 더 메모리적으로 봐도 효율적 ]이고 일반적으로 c++, java 에 사용하는 방식과 유사해서
  이런것들을 가져왔다.--> 공간적, 시간적으로 더 괜찮을 가능성이 높다 .
'''
graph = [
  [],        # 0번 노드는 없으니 무시하고. 
  [2, 3, 8], # 1번 노드는 [ 2 3 8 ] 와 연결
  [1, 7],    # 2번 노드는 [ 1 7 ]와 연결
  [1, 4, 5], # 3번 노드는 [ 1 4 5 ] 와 연결
  [3, 5],    # 4번 노드는 [ 3 5 ] 와 연결
  [3, 4],    # 5번 노드는 [ 3 4 ] 와 연결. 
  [7],       # 6번 노드는 [ 7 ] 와 연결. 
  [2, 6, 8], # 7번 노드는 [ 2 6 8 ] 와 연결.
  [1, 7]     # 8번 노드는 [ 1 7 ] 와 연결.
]

# 각 노드가 [ 방문된 정보를 리스트 자료형으로 표현 ](1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

