DFS/BFS 알아보자 🤔

DFS/BFS 처음 배울 때 (소리 없는 아우성 )

🍎DFS(Deep -First -Search)

DFS

• 깊이 우선 탐색
• 미로 찾기 /모든 노드를 방분할 때 사용

작동 원리

• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
graph = [
    [],
    [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) #  1 2 7 6 8 3 4 5 

코드설명

• graph 는 어떻게 이어져있는 나타내주는 리스트이다.
• v 는 인덱스 위치 / visited 를 통해 방문 처리 구분
• 일단 vistied [False,False,False,False,False,False,False,False,False] 넣는다
• dfs(graph, 1, visited) 재귀함수를 돌면서 방문하지 않은 graph를 찾는다.

🍎BFS(Breadth-First-Search)

BFS

• 너비 우선 탐색
• 최단 경로 할 때 사용

작동원리

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

def bfs(graph, start, visited):
    queue = deque([start])

    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
visited = [False] * 9

bfs(graph, 1, visited)  # 1 2 3 8 7 4 5 6 

코드 설명

• 방문한 시작 노드를 queue 담아논다
• vistied 배열 인덱스에 True로 바꿔놓는다.
• queue 원소가 empty 할 때 까지 반복한다
• queue 에서 popleft()하여 v 에 저장하고
• v를 print한다 # 1
• 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입