2주차에는 드디어 코딩 테스트의 꽃, 그래프 탐색(bfs/dfs)를 공부할 예정입니다.
그래프 탐색은 한국 코딩 테스트에서는 90% 이상의 확률로 출제된다고 봐도 무방할 만큼 중요하고 자주 출제되는 유형입니다.
우선 그래프 탐색을 위해서는 그래프에 대해 알아야합니다. 트리와 그래프는 가장 대표적인 그래프형 자료구조입니다.
Tree는 서로 연결된 Node의 계층형 자료구조로써, root 와 부모-자식 관계의 subtree로 구성되어 있습니다.
**그래프(G)**는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조입니다.
크게 보면 트리는 그래프의 특수한 형태입니다.
출처 : https://bigsong.tistory.com/33
| 트리 | 그래프 | |
|---|---|---|
| 정의 | 단일 루트 노드로 연결된 노드들로 이루어진 계층적인 데이터 구조. | 각각의 노드들이 엣지로 연결된 비계층적인 데이터 구조. |
| 노드 | 각 노드(루트 제외)는 정확히 하나의 부모를 가지며 사이클이 없다. | 노드들은 여러 엣지로 연결될 수 있으며 사이클이 존재할 수 있다. |
| 루트 노드 | 트리 구조에서 최상위 노드. | 그래프에는 루트 노드의 개념이 없다. |
| 방향성 vs 무방향성 | 트리는 일반적으로 무방향이다. | 그래프는 방향이 있는지, 없는지에 따라 방향성이나 무방향성이 될 수 있다. |
| 가중치 vs 무가중치 | 트리는 일반적으로 무가중치이다. | 그래프는 가중치가 있을 수 있으며(엣지가 연결된 가중치를 가짐), 없을 수도 있다. |
| 비순환성 vs 순환성 | 트리는 항상 비순환적이다(사이클이 없음). | 그래프는 비순환적일 수도 있고(사이클 없음), 순환적일 수도 있다(사이클 포함). |
| 연결성 | 모든 노드 쌍 사이에는 정확히 하나의 경로가 있다. | 그래프는 연결될 수도 있고(모든 노드가 어떤 노드에서 시작해서 다른 모든 노드에 도달 가능), 분리될 수도 있다. |
| 구성요소 | 트리는 연결된 구성요소를 가지지 않는다. | 연결된 구성요소는 모든 노드 쌍이 적어도 하나의 경로로 연결되어 있는 하위 그래프이다. |
기본 개념은 천천히 공부해보시고 여기서는 실제 문제에서 활용하는 방법을 중점적으로 다루겠습니다.