'''
    가장 기본적인 DFS 개념을 python 으로 나타낸 코드

    DFS 는 보통 스택을 활용해서 구현 하며,
    컴퓨터의 메모리 구조 자체가 스택을 이용해서 구성되어 있기 때문에,
    굳이 스택을 사용하지 않더라도, 재귀함수를 통해서 구현이 가능하다.

    이 예제에서는 총 7개의 노드가 있다고 가정하고,
    1,2,3 이 서로 인접노드 이며,
    2,4,5 가 서로 인접노드 이고,
    3,6,7 이 서로 인접노드인 그래프를 기준으로 나타내었다.
'''


def DFS(x):
    if checked[x]:
        return
    y = -1
    checked[x] = True
    print(x)
    for i in range(len(adj[x])):
        y = adj[x][i]
        DFS(y)


size = 8
checked = [False] * size  # 노드의 방문 여부를 나타내는 리스트
adj = [
    [],
    [2, 3],
    [1, 3, 4, 5],
    [1, 2, 6, 7],
    [2, 5],
    [2, 4],
    [3, 7],
    [3, 6],
]  # 인접 행렬을 나타내는 리스트

DFS(1)
