탐색 알고리즘 DFS/BFS

사전 지식

인접 행렬: 2차원 행렬로 그래프의 연결 관계를 표현하는 방식
ex. [[0, 7, 5],
[7, 0, INF],
[5, INF, 0]]

인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식
ex. [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

인접 행렬은 메모리를 잡아먹지만, 그만큼 탐색 속도가 빠르고,
인접 리스트는 메모리를 효율적으로 쓸 수 있지만, 연결된 데이터를 하나 씩 확인해야 하기 때문에 속도가 느리다.

DFS

그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다.
스택과 재귀를 이용하여 구현하고 동작 과정은 다음과 같다.
아래의 동작 과정을 꼭 숙지하자!!

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

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, v, visited)

BFS

가까운 노드부터 탐색하는 너비 우선 탐색 알고리즘이다.
큐를 이용하여 구현하고 동작 과정은 다음과 같다.
이 또한 동작 과정을 꼭 숙지하도록 하자!

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 1, 2번 반복

def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    while True:
    	v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True