항해99 TIL 1주차 -6

DFS란?

DFS란 깊이 우선 탐색이라고도 불리며 루트노드부터 시작해서 노드의 가장 깊은 부분부터 탐색하는 방법입니다.

DFS 동작 과정

DFS 동작 과정에는 스택으로 동작하는 방법과, 재귀로 동작하는 방법이 있습니다.

스택

def dfs_stack(start):
    visitor  =[]
    stack = [start]

    while stack:

        pop = stack.pop()
        visitor.append(pop)

        for adj in graph[pop]:
            if adj not in stack:
                stack.append(adj)
    return visitor  

1.루트 노드의 값을 스택에 넣는다.
2.스택에 값이 들어 있는 동안 스택에서 값을 하나 꺼낸 후 visitor 리스트에 값을 넣는다
3. 그래프[pop]의 하위 노드들 중에 스택에 값이 들어있지 않으면 스택에 값을 넣는다.
이와 같은 방법을 반복한다.

재귀함수

def dfs_recursive(index, path):
    if len(path) == len(digits):
        list.append(path)
        return
    for i in digits:
        for j in dict[digits[i]]:
             dfs_recursive(index + 1, path + j)

dict = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

list = []

dfs_recursive(0,"")

digits = "23"

1.dfs_recursive 함수에서 만약 path의 길이와 digits의 길이가 같다면 list에 path를 append하고 그렇지 않다면 for문을 반복한다.

이런 식으로 반복하다보면 "ad","ae","af","bd","be","bf"등 처음부터 끝까지 접근 할 수 있게 된다.

그래프를 표현하는 방법

인접 행렬

그래프 노드의 관계를 2차원 배열로 정리한 표현하는 방법

인접 리스트

그래프 노드의 관계를 연결리스트로 표현하는 방법