AIB 섹션 5 컴퓨터공학 N533 Search

어떤 자료구조가 있을 때 내부 자료를 어떻게 확인할 것인가. 탐색방법이 다르다고 할 수 있다. 깊이 우선: DFS, 너비 우선 BFS; depth, breadth. 미로 생각해볼 수 있다. 트리구조에 DFS는 맨 끝 child까지 보고 그 다음 sibling. BFS는 parent부터

• 자료구조에 따른 BFS, DFS 성능 차이

배울 내용: DFS, BFS, 스택 재귀 트리 그래프에 적용

S 대신 T 사용해서 traversal. 모든 노드 방문하는 것과 찾는 것과 비슷하다고 볼 수 있다.

BFS

BFS: 큐와 연관되어 있음. 위에 있는 것부터 검색된다. 재귀를 사용하지 않는다고 함

활용 예시:

• 최단 길찾기, SNS에서 연결되어 있는 사람 찾기
• 인접 노드 찾기, 그래프 문제
• 크롤링. 홈페이지 내에 카테고리를 찾고, 그 카테고리 안에 있는 카테고리나 내용을 찾아내는 방식

의사코드 중 중요한 부분으로 방문하지 않은 노드는 white이고, 이웃 노드를 탐색하는 노드는 gray. 이웃 탐색 마치면 dequeue하고 black

가장 큰 특징: 큐 사용하고, 재귀호출 하지 않음

• 노드가 적은 경우 최단경로를 탐색하는데, 큐에 쌓기 때문에 메모리 저장공간이 증가함
• 인접 노드를 확인하기 때문에 재귀할 필요 없음

장점: 최단 경로 찾기에 적합, 찾고자 하는 노드가 인접하면 효과적 단점: 큐 사용하는데 노드가 많으면 메모리 사용량도 많다. 큐는 모든 노드를 저장함.

DFS

재귀 사용할 수 있음. left node에서 right node로 옮길 때 사용한다. 스택 개념 사용한다.

탐색 전에 분할 가능한 노드를 분할한다.

백트래킹: 노드가 있을 만한 곳으로 돌아가서 살펴본다. 여기서 재귀가 적용될 수 있다.

재귀 대신 스택으로도 잘 구현할 수 있다고 함

활용 예시:

• 가중 그래프 / 스패닝
• 길 찾기

특징: 최단 거리 찾기 어렵다

장점: 찾고자 하는 노드의 depth가 깊을수록 빠르고, 메모리 적게 차지 단점: 노드가 무한개라면 무한반복

spanning tree

오후

생각해볼 점: DFS는 노드 찾으면 끝내는데, BFS는 처음 찾아도 나머지 모두 찾아보아야 한다는데… 찾으면 break나 raise StopIteration하면 되는 것 아닌가 싶음. 과연?

공간복잡도: n은 노드, m은 간선

• 인접행렬: $O(n^2)$
• 인접리스트: $O(n + m)$

기타

어떤 노드를 시작점으로 잡느냐에 따라 순서가 달라진다.