내일배움캠프 TIL

(DFS와 BFS),(그래프(Graph)와 트리(Tree) 본캠프 TIL 02/20

parkcw0325 2025. 2. 20. 20:39

DFS와 BFS의 차이를 말해주세요 

 

DFS (Depth-First Search, 깊이 우선 탐색)

동작 방식: 한 경로를 끝까지 탐색한 후 돌아와 다른 경로를 탐색합니다.

자료구조: 스택 또는 재귀 함수를 사용합니다.

특징

최단 경로를 보장하지 않지만, 메모리 사용량이 비교적 적습니다.

백트래킹이 가능해 미로 탐색, 완전 탐색(예: 모든 경우의 수 찾기)에 적합합니다.

 

 

BFS (Breadth-First Search, 너비 우선 탐색)

동작 방식: 같은 레벨의 노드를 모두 탐색한 후 다음 레벨로 넘어갑니다.

자료구조: 큐를 사용합니다.

특징

최단 경로를 보장합니다 (예: 가중치 없는 그래프).

메모리 사용량이 많지만, 노드 간 거리가 균일할 때 효율적입니다.

 

꼬리 질문 대비

Q: DFS와 BFS 중 어떤 상황에서 어떤 알고리즘을 선택하나요?

BFS: 최단 경로 탐색 (예: 네트워크 라우팅), 연결된 구성요소 전체 탐색.

DFS: 경로 존재 여부 확인, 사이클 탐지, 백트래킹이 필요한 문제 (예: 스도쿠 풀이).

 

그래프(Graph)와 트리(Tree)의 차이점

 

그래프

정의: 노드(정점)와 간선(Edge)으로 구성된 비선형 자료구조입니다.

특징

순환(Cycle)이 가능합니다.

방향성/무방향성 모두 가능합니다.

계층 구조가 없으며, 루트 노드 개념이 없습니다.

트리

정의: 그래프의 특수한 형태로, 계층적 관계를 표현합니다.

특징

순환이 없으며(DAG), 부모-자식 관계가 명확합니다.

모든 노드가 연결되어 있고(Connected), 루트 노드가 존재합니다.

노드 간 단 하나의 경로만 존재합니다.

 

꼬리 질문 대비

Q: 트리가 그래프의 하위 개념이라면, 모든 트리는 그래프인가요?

A: 네, 트리는 **사이클이 없는 연결된 그래프(Connected Acyclic Graph)**입니다.

Q: 그래프와 트리의 실제 사례를 들어 설명해주세요.


그래프: SNS 친구 관계 (순환 가능).

트리: 파일 시스템 디렉토리 구조 (계층적).