Adjeacency Matrix (인접 행렬)

✅ 인접 행렬 (Adjacency Matrix)

인접행렬의 그림

인접 행렬의 특징

그래프를 표현하는 방법 중 하나로, 2차원 리스트(배열)을 사용하여 노드 간의 연결 정보를 저장하는 방식입니다.

• 노드 개수가 N개라면, N x N 크기의 행렬을 사용합니다.
• graph[i][j] = 1이면 i번 노드에서 j번 노드로 갈 수 있음을 의미합니다.
• 무방향 그래프의 경우 graph[i][j] == graph[j][i]가 항상 성립합니다.

✅ 장점:

• 연결 여부를 빠르게 확인 가능 (O(1)) → 특정 노드 간의 연결을 빠르게 조회할 수 있습니다.
• 구현이 직관적 → 2차원 배열을 사용하기 때문에 접근이 쉬움

❌ 단점:

• 메모리를 많이 사용 (O(N^2)) → 노드 수가 많아지면 메모리 낭비가 심함
• 간선 개수가 적은 경우 비효율적 → 사용하지 않는 공간이 많아짐 (희소 그래프에서는 인접 리스트가 더 유리)

---

1️⃣인접 행렬 예제 (무방향 그래프)

다음과 같은 그래프를 인접 행렬로 표현해보겠습니다.

예제 그래프

    (0) --- (1)
     |    /
     |   /
    (2)

이 그래프의 노드(0, 1, 2)와 간선(연결선)은 다음과 같습니다:

• 0번 노드 ↔ 1번 노드
• 0번 노드 ↔ 2번 노드
• 1번 노드 ↔ 2번 노드

✅ 인접 행렬 표현

# 그래프 표현 (0번 노드, 1번 노드, 2번 노드 연결)
graph = [
    [0, 1, 1],  # 0번 노드 → 1, 2번 노드 연결
    [1, 0, 1],  # 1번 노드 → 0, 2번 노드 연결
    [1, 1, 0]   # 2번 노드 → 0, 1번 노드 연결
]

출력하면 다음과 같은 2차원 리스트가 생성됩니다.

0 1 1
1 0 1
1 1 0

---

2️⃣ 인접 행렬을 활용한 그래프 탐색

✅ BFS(너비 우선 탐색) 구현

from collections import deque

def bfs(graph, start):
    N = len(graph)
    queue = deque([start])
    visited = [False] * N
    visited[start] = True
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for next_node in range(N):
            if graph[node][next_node] == 1 and not visited[next_node]:
                queue.append(next_node)
                visited[next_node] = True
    
    print("BFS 탐색 순서:", *result)

# 그래프 입력
graph = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]

bfs(graph, 0)

출력 결과

BFS 탐색 순서: 0 1 2

---

✅ DFS(깊이 우선 탐색) 구현

def dfs(graph, node, visited):
    visited[node] = True
    print(node, end=' ')
    for next_node in range(len(graph)):
        if graph[node][next_node] == 1 and not visited[next_node]:
            dfs(graph, next_node, visited)

# 그래프 입력
graph = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]

visited = [False] * len(graph)
print("DFS 탐색 순서:", end=' ')
dfs(graph, 0, visited)

출력 결과

DFS 탐색 순서: 0 1 2

---

3️⃣인접 행렬 vs 인접 리스트 비교

방식	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
공간 복잡도	O(N^2)	O(N + E)
연결 여부 확인 속도	O(1)	O(N)
메모리 효율성	낮음 (희소 그래프에 불리)	높음 (필요한 간선만 저장)
추천 사용 경우	노드 개수가 적고 간선이 많은 경우	노드 개수가 많고 간선이 적은 경우

---

📌 마무리

인접 행렬은 그래프를 저장하고 탐색하는 대표적인 방식 중 하나입니다.

하지만 메모리를 많이 사용하는 단점이 있으므로, 노드 개수가 많을 때는 **인접 리스트(Adjacency List)**를 사용하는 것이 더 효율적일 수 있습니다.

다음 포스팅에서는 인접 리스트 방식과 비교하여 설명해보겠습니다! 🚀

더 궁금한 점이 있다면 댓글로 남겨주세요! 😊