TIL 9 | DFS와 BFS

TIL

고통스러운 알고리즘,, 개념의 벽을 느끼고 정리합니다,,,

그래프

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조

노드(Node): 연결 관계를 가진 각 데이터를 의미, 정점(Vertex)이라고도 함
간선(Edge): 노드 간의 관계를 표시한 선
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

그래프의 표현 방법

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

인접행렬에서의 adj[][]는
adj[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

• 인접 리스트(Adjacency List): 링크드 리스트로 그래프의 연결 관계를 표현

인접리스트에서 adj[]는
adj[i]: i번째 노드에 연결된 노드들을 원소로 갖는 리스트

## 인접 행렬
# 2차원 리스트를 이용한 인접 행렬

graph = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
]
# 1을 True로 0을 False로 하기도 함

## 인접 리스트
# list in dictionary 를 이용한 인접 리스트
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

# list in list
graph = [
    [],
    [2, 5, 9],
    [1, 3],
    [2, 4],
    [3],
    [1, 6, 8],
    [5, 7],
    [6],
    [5],
    [1, 10],
    [9]
]

# list in dictionary 의 인접리스트가 key 값을 이용한다면 
# list in list 방식은 index 값을 이용

이분 탐색 같은 아주 훌륭하고 효율적인 탐색법을 놔두고 왜 DFS와 BFS를 쓰는 것일까? 그 이유는 일단 전부 탐색이 필요하기 때문이라고는 하는데,, 아무튼 어딘가 필요하기 때문에 배우는 것이겟지,,, 화나는 건 당연하지만 침착하고 꼼꼼하게 살펴보도록 하자.

DFS (Depth First Search)

말그대로 '깊이 우선 탐색'이다.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
갈 수 있을 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조.

실행과정을 보자면

• 노드를 방문하고 깊이 우선으로 인접한 노드를 방문
• 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문
• 만약 끝에 도달했다면 리턴

등등.. 설명은 다양하지만 못생긴 포도송이 그림으로 보면 이해가 빠르다.

얄밉고 못생긴 포도송이

DFS는 두가지의 방식으로 구현할 수 있다.
첫번째, 재귀함수
둘째, 스택

DFS의 동작 원리는 기본적으로 스택 자료구조이고 재귀함수로 구현하는 것이 일반적.

재귀함수로 구현

1 루트 노드부터 시작한다.
2 현재 방문한 노드를 visited에 추가한다.
3 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4 2부터 반복.

# Q. 인접 리스트가 주어질 때, 모든 노드를 DFS 순서대로 방문하시오.

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
  
visited = []

def dfs_recursion(adjacent_graph, cur_node, visited_array):
  visited_array.append(cur_node)
  for adjacent_node in adjacent_graph[cur_node]:
  	if adjacent_node not in visited_array:
  		dfs_recursion(adjacent_graph, adjacent_node, visited_array)  
  return visited_array

dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력!@!@!

스택으로 구현

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

# Q. 인접 리스트가 주어질 때, 모든 노드를 DFS 순서대로 방문하시오.

graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
}

def dfs_stack(start_node, adjacent_graph):
    visited = []
    stack = [start_node]
    while stack:
	cur_node = stack.pop()
	visited.append(cur_node)
	for adjacent_node in adjacent_graph[cur_node]:
	    if adjacent_node not in visited:
		stack.append(adjacent_node)
    return visited

print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력!@@@@@@@!!!!!

여기서 '아~ dfs는 재귀함수와 스택으로 구현할 수 있구나아~' 하고 돌아선다면 크게 낭패를 보고 문제를 풀다가 알고리즘 부모님의 안부를 묻는 비극적인 상황을 마주할 수 있다.

다시 말하자면 DFS를 푸는 방법에는 두가지가 있다. 그리고.... 그 두가지 방법은 다른 결과를 보여준다. 자세히 보면 두 방법이 return한 결과는 다르다는 것을 볼 수 있다. 왜 이런 차이점일 생기는 걸까?

바로 가장 깊이 탐색한다는 방식은 같으나 구현 방식과 탐색하는 순서에 차이가 있다.

graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
}

재귀 방식이 1 -> [2, 5, 9]의 2 -> [1, 3]의 3 -> ... 처럼 인접 리스트의 작은 수부터 체크 하는 방식이라면,
스택 방식은 1 -> [2, 5, 9]를 스택에 넣고 -> 9 -> [10]를 스택에...같이 시작노드에 해당하는 인접 리스트를 전부 스택에 넣고 시작하기 때문에 차이가 발생한다.

둘다 DFS라는 점에서 큰 의미가 없다고 생각할 수 있지만 이를 이해하고 접근한다면 문제를 풀다가 감정소모를 하게되는 안타까운 상황을 피할 수 있을 것이라고 생각한다.

BFS (Breadth First Search)

BFS 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다.
쉽게 말해 가까운 노드부터 탐색하는 알고리즘!!
최대한 깊은 곳부터 탐색하는 DFS와 달리 인접 노드들을 전부 훑고 지나간다.

못생긴 포도를 통해 빠르게 살펴보자.

BFS의 동작 원리는 큐 방식이기 때문에 큐 자료구조를 이용해서 구현할 수 있다.

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

# Q. 인접 리스트가 주어질 때, 모든 노드를 BFS 순서대로 방문하시오.

import deque

graph = {
  1: [2, 3, 4],
  2: [1, 5],
  3: [1, 6, 7],
  4: [1, 8],
  5: [2, 9],
  6: [3, 10],
  7: [3],
  8: [4],
  9: [5],
  10: [6]
}


def bfs_queue(adj_graph, start_node):
  visited = []
  queue = deque[start_node]
  while queue:
      n = queue[0]
      visited.append(queue.leftpop())
      for adjacent_node in adj_graph[n]:
          if adjacent_node not in visited:
              queue.append(adjacent_node)
  return visited


print(bfs_queue(graph, 1))  # 1 이 시작노드입니다!
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력@!@!!@!@!!!

BFS의 구현에는 .pop(0)이 사용되기 때문에 내장함수인 deque를 활용한다면 시간복잡도를 고려한 효율적인 코드를 구현할 수 있다.