[Python] 알고리즘 개념13 - 그래프(Graph)와 탐색 (BFS, DFS)

 

 

🚀 1. 그래프(Graph)란?

**그래프(Graph)**는 노드(Node)와 간선(Edge)으로 이루어진 자료구조예요.

 

💡 쉽게 이해하기

• 🏙 지하철 노선도처럼 여러 지점(노드)이 선(간선)으로 연결된 구조예요.
• 🔄 네트워크, 지도, 경로 탐색 등에 활용돼요.

 

📌 그래프의 기본 개념

• 정점(Vertex, Node): 그래프의 한 지점
• 간선(Edge): 정점 간의 연결선
• 인접 노드(Adjacent Node): 간선으로 연결된 노드
• 가중치(Weight): 간선에 부여된 값 (예: 거리, 비용 등)

 

📌 그래프의 종류

1. 무방향 그래프(Undirected Graph) → 간선이 양방향으로 연결됨
2. 방향 그래프(Directed Graph, DAG) → 간선이 한쪽 방향으로만 연결됨
3. 가중치 그래프(Weighted Graph) → 간선에 가중치가 부여됨

➡ 그래프는 다양한 문제 해결에 활용돼요!

---

 

 

🚀 2. 그래프 표현 방법

그래프는 **인접 행렬(Adjacency Matrix)**과 **인접 리스트(Adjacency List)**로 표현할 수 있어요.

 

📌 1) 인접 행렬 (Adjacency Matrix)

• ⚡ 2차원 배열을 이용하여 노드 간 연결 관계를 저장
• ⏳ 모든 노드 간 연결 여부를 O(1)으로 확인 가능하지만, 메모리 사용이 많음

 

💡 인접 행렬 예시

graph = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [1, 1, 0, 1],
    [0, 1, 1, 0]
]

➡ 노드 간의 연결 관계를 행렬로 표현해요!

 

📌 2) 인접 리스트 (Adjacency List)

• ⚡ 각 노드가 연결된 노드만 저장하는 방식
• 📌 메모리 효율이 좋고, 연결된 노드 탐색이 빠름

 

💡 인접 리스트 예시

graph = {
    1: [2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [2, 3]
}

➡ 연결된 노드만 저장하여 공간을 절약해요!

---

 

 

🚀 3. 깊이 우선 탐색(DFS, Depth First Search)

**DFS(깊이 우선 탐색)**은 한 방향으로 깊이 탐색하다가 막히면 다시 돌아오는 방식이에요.

 

📌 DFS의 특징

• 🏞 미로 탐색, 백트래킹 문제에서 자주 사용
• 🛠 스택(Stack) 또는 재귀(Recursion)로 구현 가능

 

💡 DFS 구현 (재귀 방식)

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 그래프 정의
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
visited = set()
dfs(graph, 1, visited)  # 출력: 1 2 4 3

➡ 재귀적으로 탐색하며, 방문한 노드를 출력해요!

---

 

 

🚀 4. 너비 우선 탐색(BFS, Breadth First Search)

**BFS(너비 우선 탐색)**은 가까운 노드부터 탐색하는 방식이에요.

 

📌 BFS의 특징

• 🚂 최단 경로 문제에서 자주 사용 (예: 최단 거리 찾기)
• 📌 큐(Queue)를 이용하여 구현

 

💡 BFS 구현 (큐 사용)

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 그래프 정의
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
bfs(graph, 1)  # 출력: 1 2 3 4

➡ 가까운 노드부터 탐색하며, 큐를 이용해 관리해요!

---

 

 

🚀 5. DFS vs BFS 비교

 

방식 - DFS (깊이 우선 탐색) / BFS (너비 우선 탐색)

탐색 방식	한 방향으로 깊이 탐색	가까운 노드부터 탐색
자료구조	스택 (재귀 or 명시적)	큐 사용
활용 예시	백트래킹, 경로 찾기	최단 경로 찾기

➡ DFS는 깊이 있는 탐색이 필요할 때, BFS는 최단 거리 문제에 사용해요!

---

 

 

🚀 6. 그래프 탐색 활용 예시

📌 그래프 탐색은 어디에서 사용될까요?

1. 지도 탐색(네비게이션 경로 탐색) → 최단 거리 찾기(BFS 활용)
2. 웹 크롤링(인터넷 검색 엔진) → DFS로 페이지 탐색
3. SNS 친구 추천 시스템 → 그래프 탐색으로 연결된 친구 찾기
4. 퍼즐 게임 (예: 미로 탈출) → DFS/BFS 활용하여 해결

➡ 그래프 탐색은 실생활에서도 매우 유용하게 사용됩니다! 😊

---

 

 

✅ 마무리 정리

• 그래프는 노드와 간선으로 이루어진 자료구조로, 지도, 네트워크 등에 활용됩니다.
• DFS는 깊이 우선 탐색 방식으로, 한 방향으로 끝까지 탐색합니다.
• BFS는 가까운 노드부터 탐색하는 방식으로, 최단 경로 문제에 유용합니다.
• DFS는 백트래킹 문제, BFS는 최단 거리 문제 해결에 활용됩니다.