알고리즘

[알고리즘] DFS/BFS

꿈꿈개 2022. 8. 9. 22:13

DFS

DFS(Depth-First Search)는 깊이 우선 탐색 알고리즘이다.

그래프에서 깊은 부분을 우선으로 탐색하는 것이다. 

 

그래프가 그럼 뭘까?

그래프는 Node(혹은 정점이라고 부르기도함(vertex))와 Edge(간선)로 표현된다.

예를 들어 노드를 장소, 간선을 거리라고 생각할 수도 있다. 약국에서 병원까지의 거리를 3km, 약국에서 학교를 5km라고 한다면 아래 이미지처럼 표현할 수 있다.

  약국 병원 학교
약국 0 3 5
병원 3 0 무한
학교 5 무한 0

※ 연결되지 않은 노드는 무한으로 표현한다

 

그래프는 두가지 방식으로 표현된다.

  • 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현
  • 인접 리스트 : 리스트로 그래프의 연결관계를 표현

인접행렬(Adjacency Matrix)

INF= 999999999

graph=[
    [0,3,5],
    [3,0,INF],
    [5,INF,0]
]

인접리스트(Adjacency List)

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결

넘 못 그렸당 ㅎㅎ

인접행렬 처럼 모든 노드의 관계를 저장하지 않아도 되어 인접리스트가 메모리 효율에 있어서는 좋다.

하지만 이 때문에 인접리스트 방식은  특정한 두 노드가 연결되어있는지 연결된 데이터를 하나씩 찾아봐야하기 때문에  대한 정보를 얻는 속도는 느리다. 

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

graph[0].append((1,3))
graph[0].append((2,5))
graph[1].append((0,3))
graph[2].append((0,5)) #-> [[(1, 3), (2, 5)], [(0, 3)], [(0, 5)]]

 

그래프에 대해 알았으면 다시 DFS로 가보자

위에서 설명한 그래프에서 제일 깊은 위치의 노드를 확인할때까지 탐색하는 것을 깊이우선탐색 알고리즘이라고 하는 것이다. 

 

DFS의 동작 과정은 이렇다

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스펙에 넣고 방문처리.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

 

DFS 구현 코드

def dfs(graph, v, visit) :
	#현재 노드 방문 처리
    visit=True
    
    for i in graph[v] :
    	if not visit[i] :
        	dfs(graph, i, visit)
#각 노드가 연결된 정보를 리스트로 표현(2차원 리스트)
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visit=[False]*9

dfs(graph, 1, visit)
#결과
12768345

 

 

DFS의 시간 복잡도 : O(N)

 

 

 

BFS

BFS(Breadth First Search) 는 너비 우선 탐색 알고리즘이다. 가까운 노드부터 탐색하는 알고리즘으로 최단 경로를 찾는데 적합한 알고리즘이다.

DFS는 최대한 멀리 있는 노드부터 우선 탐색하는거에 반대인 셈이다. 

BFS는 큐 자료구조를 사용한다.

 

동작방식

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 함

2. 노드를 큐에서 꺼내고 해당 노드의 인접한 노드를 큐에 삽입해 방문 처리함

3. 2번의 과정을 더이상 수행할 수 없을 떄까지 반복

 

구현코드

from collections import deque

def dfs(graph, v, visit) :
    queue=deque([v])

	#현재 노드 방문 처리
    visit[v]=True
    
    while queue :
        queue.popleft()
        #해당 노드에 인접하지만 방문하지 않은 노드 탐색a
        for i in graph[v] :
            if visit[i]==False :
                queue.append(graph[i])
                visit[i]=True
                
           
graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visit=[False]*9

dfs(graph, 1, visit)
#결과
12387456

BFS 시간복잡도 : O(N)

 

일반적으로 DFS보다 수행시간 효율이 좋은편이라는데 그 이유는 추후에 찾아봐야겠다!

 

즉 정리하면 DFS는 스택, 재귀함수를 사용한다는것

BFS는 큐, degue라이브러리를 주로 사용한다는것을 기억해두자

 

 

※이 포스팅은 <이것이 취업을 위한 코딩테스트다(나동빈 저)>를 참고하여 작성하였습니다,