DFS 구현을 위한 자료구조.

스택.

오버플로 : 자료구조에 데이터의 크기까지 가득 찬 상태에서 삽입연산을 수행할 때 발생.
언더플로 : 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생.

스택이란?
선입후출(First In Last Out)구조 또는 후입선출(Last In Frist Out)구조라 한다.

파이썬의 경우 별도의 라이브러리를 사용할 필요 없다.
append()와 pop() 를 이용해 동일하게 동작한다.

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)
print(stack[::-1])

재귀.

• 자기 자신을 다시 호출하는 함수를 의미함.

재귀 호출을 하다 보면 발생하는 에러가 있는데.<1000번을 제한한다고 한다.>

RecursionError: maximum recursion depth exceeded while calling a Python object

이러한 상황에는 sys.setrecursionlimit(number) 재귀 횟수의 리밋을 걸어줌으로써 실행 가능하다.

• 중요한 점 : 종료 조건을 꼭 명시해야 한다.(기저사례가 중요.)

팩토리얼 재귀.

def factorial(N):
    if N <= 1:
        return 1
    return N * factorial(N - 1)

재귀의 경우 점화식을 자주 이용하는데 이는 나중에 DP로 가기 위한 중요한 점이다.

DFS

• 깊이 우선 탐색. (그래프의 깊은 부분을 우선적으로 탐색하는 것)

인접 행렬 : 2차원 배열에 그래프의 연결 관계를 표현.(모든 노드에서의 연결관계를 표시한다.)

INF = 999999999
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

장점 : 두 노드의 연결 여부에 대한 확인이 빠름.
단점 :메모리가 불필요하게 낭비됨.(모든 노드의 연결관계를 나타내기 때문에)

인접 리스트 : 연결된 노드에 대한 정보만 리스트에 append()하는 것.

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))

graph[2].append((0, 5))

장점 : 메모리를 효율적으로 사용.
단점 : 두 노드의 연결 여부에 대한 확인은 느림.

DFS의 동작 과정.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리를 한다.
   방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. (2.)의 과정을 반복한다.

def DFS(graph, node, visit):
    visit[node] = True
    print(node, end=" ")

    for next_node in graph[node]:
        if not visit[next_node]:
            DFS(graph, next_node, visit)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [5, 6],
    [3, 4],
]
visit = [False] * 6
DFS(graph, 1, visit)