우리가 지금까지 배운 트리(Tree)는 부모와 자식이라는 계층이 있는 깔끔한 구조였습니다. 하지만 현실은 그렇게 깔끔하지 않습니다. 지하철 노선도는 얽히고설켜 순환선이 되기도 하고, 페이스북 친구 관계는 촌수 따위 없이 거미줄처럼 연결됩니다. 이렇게 복잡한 네트워크 연결 망을 표현하기 위해 탄생한 자료구조가 바로 그래프(Graph)입니다. 그리고 이 미로 같은 그래프 속에서 길을 찾는 방법이 바로 코딩 테스트의 단골 손님인 DFS와 BFS입니다.
1. 그래프(Graph)란? (트리와의 차이점)
그래프는 점(Vertex/Node)과 그 점들을 잇는 선(Edge)으로 이루어진 자료구조입니다. 트리와 가장 큰 차이점은 '순환(Cycle)'입니다. 트리는 밑으로 내려갔다가 다시 위로 돌아올 수 없지만, 그래프는 빙글빙글 도는 순환 구조가 가능합니다. 또한 '루트 노드(시작점)'나 '부모-자식' 개념이 없습니다. 모든 점은 평등합니다.
- 방향 그래프: 일방통행 도로처럼 화살표가 있는 그래프 (인스타그램 팔로우)
- 무방향 그래프: 양방향 도로처럼 선만 있는 그래프 (페이스북 친구)
- 가중치 그래프: 선에 비용(거리, 시간)이 적혀 있는 그래프 (지하철 노선도 소요시간)
2. 그래프를 여행하는 두 가지 방법
복잡한 미로(그래프)에 갇혔을 때 탈출구를 찾는 전략은 크게 두 가지가 있습니다.
2-1. 깊이 우선 탐색 (DFS: Depth-First Search)
"한 놈만 팬다" 전략입니다. 갈림길이 나오면 무조건 한쪽 길을 정해 막다른 곳이 나올 때까지 끝까지 파고듭니다. 막히면 바로 직전 갈림길로 돌아와(Backtracking) 다른 길을 갑니다.
- 구현: 스택(Stack)이나 재귀 함수를 사용합니다.
- 특징: 미로 찾기처럼 '경로가 존재하는지' 확인할 때 유용합니다. 코드가 비교적 간결합니다.
2-2. 너비 우선 탐색 (BFS: Breadth-First Search)
"돌다리도 두들겨 보고" 전략입니다. 시작점에서 가까운 곳부터 하나씩 모두 방문하고, 그다음으로 먼 곳을 방문합니다. 마치 호수에 돌을 던지면 물결이 동그랗게 퍼져나가는 것과 같습니다.
- 구현: 큐(Queue)를 사용합니다. (FIFO)
- 특징: 출발지에서 목적지까지의 '최단 경로'를 보장합니다. 내비게이션이 길을 찾을 때 이 방식을 기본으로 합니다.
3. 실무에서의 그래프 활용
그래프는 '연결'된 모든 것을 표현할 수 있습니다.
- 소셜 네트워크 서비스(SNS): "알 수도 있는 친구" 추천 기능은 내 친구의 친구들을 그래프 탐색으로 찾아내는 것입니다.
- 내비게이션(길 찾기): 교차로를 정점, 도로를 간선으로 보고 BFS나 다익스트라 알고리즘을 돌려 최단 시간 경로를 계산합니다.
- 웹 페이지 크롤링: 구글 검색 봇은 하나의 링크(정점)를 타고 들어가 연결된 다른 링크(간선)들을 계속 탐색하며 전 세계 웹을 긁어모읍니다.
[핵심 요약]
1. 그래프는 점과 선으로 연결 관계를 표현하는 비선형 자료구조로, 순환(Cycle)이 가능합니다.
2. DFS(깊이 우선)는 스택을 써서 한 우물만 파고, BFS(너비 우선)는 큐를 써서 주변부터 훑습니다.
3. 최단 경로 찾기(내비게이션), 친구 추천, 네트워크 분석 등 복잡한 연결 문제 해결의 열쇠입니다.
1. 그래프는 점과 선으로 연결 관계를 표현하는 비선형 자료구조로, 순환(Cycle)이 가능합니다.
2. DFS(깊이 우선)는 스택을 써서 한 우물만 파고, BFS(너비 우선)는 큐를 써서 주변부터 훑습니다.
3. 최단 경로 찾기(내비게이션), 친구 추천, 네트워크 분석 등 복잡한 연결 문제 해결의 열쇠입니다.