DFS BFS - Concept

 

 

해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.

 

탐색 알고리즘

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- DFS, BFS

 

 

자료구조

스택

- 후입선출

- list로 구현, append() , pop()

- 재귀함수의 수행방식

 

큐

- 선입선출

- deque로 구현, append(), popleft()

- deque는 list보다 데이터 삽입, 삭제가 빠름

 

오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생

언더플로 : 데이터가 없는 자료구조에서 삭제 연산을 수행할 때 발생

 

(+)프로그래밍에서 그래프는 크게 2가지로 표현가능

- 인접 행렬 : 2차원 배열에서 각 노드와 나머지 모든 노드에 대해서 연결된 형태를 기록하는 방식

(단점 : 불필요한 메모리 사용)

- 인접 리스트 : 모든 노드에서 연결된 노드에 대한 정보를 차례대로 연결하여 저장

(단점 : 특정노드와 특정노드가 서로 연결되었는지 확인하려면 시간이 오래걸림)

 

-> 나는 보통 인접리스트를 많이 사용하는 것 같다 

 

DFS (깊이 우선탬색)

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 자료구조에 기초한 알고리즘

- 탐색 시간 복잡도 : O(N)

- 구현 : 재귀함수 사용, 방문처리 리스트 필요

 

"특정 노드와 연결된 노드들 중에 하나의 노드를 선택하여 스택에 넣고 방문처리 이 후, 뒤에서 부터 다시 하나씩 빼며 탐색"

"맵을 생각한다면 상하좌우 이동 - 상하좌우 이동 - ... 방식"

 

 

BFS (너비 우선탐색)

- 가까운 노드부터 탐색하는 알고리즘

- 큐 자료구조에 기초한 알고리즘

- 탐색 시간 복잡도 : O(N)

- 구현 : 큐자료구조 이용, 방문처리 리스트 필요

 

"특정노드와 연결된 노드들 중에 모든 노드를 선택하여 큐에 넣고 방문처리 이 후, 앞에서 부터 다시 하나씩 빼며 탐색"

"맵을 생각한다면 상상상상... - 하하하하하하.... 왼왼왼... 방식"

 

 

 

유형 정리

- 공통적으로 노드-간선 구조

- 시간복잡도는 O(N)

 

DFS

- 연결된 노드집합의 수 구하기

- 연결된 노드집합 판단

 

BFS

- 간선이 1일 때, 노드에서 노드까지 가장 짧은 거리 구하기

- 간선이 1일 떄, 특정노드와의 거리가 k인 노드

 

모든 간선의 길이가 1인 그래프