py) BFS, DFS

DFS(Depth First Search) 깊이 우선 탐색

: 시작 노드를 방문처리 하고 방문처리 되지 않은 노드로 진행 선택된 노드는 방문처리 되고 새로운 시작 노드가 되어 같은 방법을 반복하다가 방문처리 되지 않은 노드가 없을 경우 되돌아 감

BFS(Breadth First Search) 너비 우선 탐색

: 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문. 시작 노드에서 인접한 노드들을 방문하고 그 노드들과 인접한 노드들을 방문

 

DFS

-구현 가능한 방법 또는 활용하는 자료구조: 1. 순환호출(재귀함수) 2. 스택(Stack)

- 순환호출 이용

 

 

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
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9 #방문을 체크하기 위한 빈 리스트 (방문안됨 처리)

dfs(graph, 1, visited)
#1번 노드부터 방문 시작

 

BFS

-사용하는 자료구조: 큐(Queue)

 

 

from collections import deque   #deque 사용

def bfs(graph, start, visited):
    queue = deque([start])  #queue 사용
    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
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9 #방문을 체크하기 위한 빈 리스트 (방문안됨 처리)

bfs(graph, 1, visited)
#1번 노드부터 방문 시작

 

느낀점: 이 코드만 외운다거나 꽂히거나 할 게 아니라 개념을 이해해서 문제에 따라 잘 활용하는게 필요!

참고 - youtu.be/7C9RgOcvkvo