DFS / BFS

📗 DFS & BFS

• 탐색 알고리즘
  • DFS와 BFS는 그래프 탐색 알고리즘에 속하며, 그래프의 모든 꼭짓점을 방문하는 알고리즘을 의미함
  • 트림 탐색은 그래프 탐색의 특수 일종이며, 방문한 노드는 다시 방문하지 않음

🔔 Graph

• 그래프는 노드와 간선으로 이루어진 자료구조의 일종
• 그래프 구현 방식
  1. 인접 행렬 : 2차원 배열을 활용한 방식
     • 장점 : 두 노드의 간선 존재 여부를 바로 파악할 수 있음
     • 단점 : 모든 관계를 기록하므로 노드의 수가 많을 수록 메모리 낭비가 생김
  2. 인접 리스트 : 연결리스트를 활용한 방식
     • 장점 : 연결된 것만 기록하여 특정 노드의 인접 노드를 바로 파악할 수 있음
     • 단점 : 두 노드가 연결되어 있는지 확인하는데 인접 행렬보다 오래걸림
• 따라서 인접행렬은 그래프에 간선이 많이 존재하는 밀집 그래프일 때, 인접 리스트는 간선이 적은 희소 그래프일 경우에 사용함
  

🔔 DFS

• 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
• 시간복잡도 : O(N)
• 스택 구현 방법
  1. 빈 스택에 시작할 노드를 넣음
  2. 스택에서 노드를 pop하고 출력, 꺼낸 노드의 자식 노드를 다 넣음 (이때 한 번 스택에 담은 노드는 다시 넣지 않음)
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복
  - 스택을 사용하므로 마지막으로 넣은 노드부터 탐색됨
• 재귀 구현 방법
  1. 노드의 자식의 자식...을 계속 호출함
  2. 더 이상 자식이 없는 경우 한 단계 올라와서 그 지점의 다른 경로부터 탐색을 다시 시작함
  - 구현 시 스택을 사용하지 않아도 되므로 코드가 깔끔함

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]
visited = [False] * 8

# 재귀 구현
def recursive_dfs(v):
	visited[v] = True
    # print(v, end = '')
    for i in graph[v]:
    	if not visited[i]:
        	recursive_dfs(i)
recursive_dfs(1)

# 스택 구현
def iterative_dfs(v):
	visited=[]
    stack = [v]
    while stack:
    	v = stack.pop()
        if v not in visited:
        	visited.append(v)
            for w in graph[v]:
            	stack.append(w)
    return visited
iterative_dfs(1)

🔔 BFS

• 그래프의 너비부터 탐색하여 시작 노드로부터 가까운 지점을 먼저 방문하고 먼 지점은 나중에 방문함
• 무한한 길이를 가지는 경로가 존재할 때 탐색 목표가 다른 경로에 있는 경우, 모든 경로를 동시에 진행하므로 탐색이 가능함
• 큐로 구현이 가능하며 재귀로 구현은 불가능함
• 시간복잡도 : O(N) - BFS보다 조금 더 빠르게 동작함
• 큐 구현 방법
  1. 빈 큐를 만들고 시작 노드를 넣음
  2. 큐에서 pop하고 출력함, 꺼낸 노드의 자식들을 큐에 추가함 (이때, 한 번 큐에 담은 노드는 다시 넣지 않음)
  3. 2번 과정을 더 이상 수행할 수 없을때까지 반복

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]
visited = [False] * 8

from collections import deque
def bfs(v):
	q = deque()
    q.append(v)
    while q:
    	x = q.popleft()
        # print(x, end='')
        for i in graph[x]:
        	if not visited[i]:
            	q.append(i)
                visited[i] = True
bfs(1)

🔔 DFS / BFS의 응용

• DFS의 장점
  - 한 경로상의 노드만 기억하므로 적은 메모리를 사용함
  - 목표 노드가 깊은 단계에 있는 경우 빠르게 탐색 가능

• DFS의 단점
  - 무한한 길이를 가지는 경로가 존재하는 경우 영원히 종료하지 못함
  - 목표에 이르는 경로가 다수인 경우, 해에 도착하면 탐색을 종료하므로 얻은 해가 최단 경로라는 보장이 없음

• BFS의 장점
  - 모든 경로를 탐색하므로 여러 해가 존재해도 최단 경로를 보장함
  - 무한한 길이의 경로가 존재해도 해를 찾을 수 있음
  - 노드의 수가 적고, 깊이가 얕은 해가 존재할 때 유리함

• BFS의 단점
  - 노드의 수가 많을수록 많은 메모리를 필요로 함 (그래프에 비례하는 공간복잡도를 가짐)
  
  

📘 관련 문제

⭐ 타겟넘버
⭐ 네트워크
⭐ 게임 맵 최단거리
⭐ 단어변환
⭐ 아이템 줍기
⭐ 여행경로