[알고리즘] DFS / BFS

본격적인 취업 준비 시작을 위핸 알고리즘 공부 스타토!

일단 기존에 알고 있는 알고리즘들을 복습하는 시간들을 갖고자 한다.

Depth-First-Search

깊이 우선 탐색 알고리즘
해당 알고리즘은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
해당 개념을 여기서 다루진 않을 것이며, 그래프를 표현 하는 방식부터 짚고 넘어갈 예정이다.

인접행렬

2차원 배열로 그래프의 연결 관계를 표현하는 방식

2차원 배열에 각 노드가 연결된 형태 및 가중치를 기록하는 방식이다.

구체적인 예시로 AB 노드는 1행2열에 1로 표시되어 있으므로 연결되어 있는 상태이며 3행 2열 B와 C 노드를 보면 0으로 되어있으며 노드간 연결이 끊겨있다.
파이썬 코드로 해당 그래프를 구현하면 아래와 같은 형식으로 표현할 수 있다.

graph = [[0, 2, 3],
		[2, 0, 4],
        [3, 4, 0]]

인접 리스트

리스트로 그래프의 연결 관계를 표현하는 방식
인적 리스트 방식에서는 모든 노드ㅡ에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

인접 리스트를 파이썬으로 구현하면 아래와 같다.

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

# 노드 0에 연결된 노드의 정보를 입력(연결된 노드, 가중치) > 튜플의 형태
graph.append((1, 7))
graph.append((2, 5))

# 노드 1에 연결된 노드의 정보를 입력
graph.append((0, 7))

# 노드 2에 연결된 노드의 정보를 입력
graph.append((0, 5))

두방식의 차이점

둘의 관계는 서로 trade off 관계이다.

인접행렬 방식은 관련된 모든 관계를 저장하기 때문에 메모리 측면에서 손해를 본다. 그러나 위의 방식은 특정한 두 노드에 대한 정보를 빠르게 찾을 수 있다.
인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리 측면에서 이득이 있으나 특정한 노드에 대한 정보를 확인하려면 해당 노드에 연결된 데이터를 하나씩 확인해야 한다.

DFS 예제 코드 구현

def dfs(graph, v, visited):
    visited[v] = True # 첫번째 노드 방문
    print(v, end=" ")

    for i in graph[v]: # 첫번째 노드에서 순서대로 탐색을 진행한다.
        if visited[i] == False:    
            visited[i] = True # 해당 노드를 방문처리 한 후
            dfs(graph, i, visited) # 다시 아래 노드들을 탐색한다.   만약 해당 노드가 방문된 상태라면? 그냥 아무것도 안하면 된다.
    else: # for문이 다끝나면 해당 함수를 종료한다.
        return 

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * len(graph)
dfs(graph, 1, visited)

BFS 예제 코드 구현

from collections import deque

def bfs(graph, start, visited):
    # deque instance 생성
    queue = deque()
    # 큐에 start 추가 및 방문했다는 표시 
    queue.append(start)
    visited[start] = True

    # 큐가 빌때까지 해당 반복문 시작
    while queue:
        #  큐에 추가된 노드를 꺼낸다. 
        current_node = queue.popleft()
        print(current_node, end=" ")
        # 해당 노드와 연결된 노드들을 확인한다. 
        for i in graph[current_node]:
            if not visited[i]: # 해당 노드들중 방문하지 않은 아이들을 방문 처리 후 큐에 추가한다. 
                visited[i] = True
                queue.append(i)

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * len(graph)
bfs(graph, 1, visited)

### 시간 복잡도 O(n^2)

![](https://velog.velcdn.com/images/hyunwoozz/post/7cb00d2b-0b02-481a-b761-5f6c34fd7a66/image.png)