[자료구조 & 알고리즘] BFS 알고리즘 구현 시 자료구조[배열/리스트]를 선택하는 방법과 이유(feat. 밀집그래프, 희소그래프)

문제: 연결 요소의 개수 (BOJ 11724)

https://www.acmicpc.net/problem/11724

 

해당 문제를 배열과 리스트 두가지 방법으로 구현했으나 매모리와 속도 측면에서 차이가 발생했습니다.

결과를 분석하고 BFS를 구현할 때 배열과 리스트중 적합한 자료구조를 선택하는 방법과 이유에 대해 알아보겠습니다.

 

한줄요약: 밀집 그래프 = 배열 / 희소 그래프 = 리스트 

 

 

하단의 두 링크는 해당 문제에 대한 코드와 풀이 입니다.

 

BFS + 배열

https://rnasterofmysea.tistory.com/48

 

BFS + 리스트

https://rnasterofmysea.tistory.com/49

---

백준 결과 분석

1. 메모리 사용량

• 배열 기반: 5024 KB
  배열 기반 구현에서는 1차원 배열을 사용하여 인접 행렬을 표현했기 때문에, 그래프 크기 N×N에 따라 고정된 크기의 메모리를 사용합니다. 하지만 메모리 낭비가 적으며, 방문 여부와 큐를 저장하는 데 최소한의 메모리만 필요합니다.
• 리스트 기반: 32268 KB
  리스트 기반 구현에서는 동적 메모리 할당을 통해 연결 리스트를 구성합니다. 연결 리스트는 각 노드마다 추가적인 포인터(다음 노드를 가리키는 주소)를 저장해야 하므로, 배열 기반보다 메모리 사용량이 더 큽니다. 특히 노드의 개수가 많아질수록 메모리 오버헤드가 발생합니다.

결론: 메모리 사용량은 배열 기반이 더 효율적입니다.

---

2. 실행 시간

• 배열 기반: 116 ms
  배열 기반 구현에서는 인접 행렬을 사용하기 때문에 노드 간의 연결 여부를 확인하는 연산이 O(1)입니다. 이는 리스트 기반의 O(Degree)에 비해 빠릅니다. 따라서 BFS나 DFS 수행 시, 간선 탐색 시간이 더 짧아집니다.
• 리스트 기반: 336 ms
  리스트 기반 구현에서는 인접 리스트를 순회해야 하므로, 각 노드에 연결된 간선을 순회하는 시간 복잡도가 O(Degree)입니다. 간선의 수가 많을수록 탐색 시간이 증가합니다.

결론: 실행 시간은 배열 기반이 더 빠릅니다.

---

3. 코드 길이

• 배열 기반: 1565 Bytes
  배열 기반은 구현이 간단합니다. 간선의 유무를 저장하거나 탐색할 때 고정된 인덱스로 접근하므로 코드가 직관적이고 간결합니다.
• 리스트 기반: 2422 Bytes
  리스트 기반은 간선 추가를 위한 동적 메모리 할당, 연결 리스트의 관리 등 추가적인 코드가 필요합니다. 따라서 배열 기반보다 코드 길이가 길어질 수밖에 없습니다.

결론: 코드 길이는 배열 기반이 더 간결합니다.

---

비교 표

아래는 제공된 배열 기반 코드와 리스트 기반 코드를 비교한 표입니다.

 

항목	배열 기반	리스트 기반
메모리 사용량	5024 KB	32268 KB
실행 시간	116 ms	336 ms
코드 길이	1565 Bytes	2422 Bytes
그래프 표현 방식	1차원 배열로 인접 행렬 표현	연결 리스트로 인접 리스트 표현
시간 복잡도 (탐색)	O(N^2) (노드 전체를 순회, 빠른 간선 확인)	O(N+M) (연결된 노드만 탐색)
시간 복잡도 (삽입)	O(1) (고정된 인덱스 접근)	O(1) (연결 리스트 삽입)
공간 복잡도	O(N^2)	O(N+M)
적합한 그래프	밀집 그래프	희소 그래프
코드 구현 난이도	간단 (인접 행렬 표현, 고정 인덱스 접근)	복잡 (동적 메모리 할당 및 관리 필요)
간선 추가/삭제	어렵다 (고정 크기 배열 변경 어려움)	쉽다 (동적 메모리로 간선 삽입/삭제 가능)
장점	빠르고 간단하며, 고정된 메모리 구조로 직관적임.	메모리 효율적 (특히 희소 그래프에서 유리).
단점	메모리 낭비 (희소 그래프에서 비효율적).	탐색이 느리고 동적 메모리 관리가 복잡함.

---

적합한 선택 기준

1. 그래프의 특성:
   • 밀집 그래프 : 배열 기반이 더 적합.
   • 희소 그래프 : 리스트 기반이 메모리와 시간 면에서 더 효율적.
2. 그래프의 크기:
   • 노드 수와 간선 수가 작으면, 배열 기반과 리스트 기반의 차이가 크지 않음.
   • 노드 수와 간선 수가 매우 크면, 리스트 기반이 더 효율적.
3. 응용:
   • 특정 간선 존재 여부를 자주 확인해야 한다면 배열 기반.
   • 간선의 추가/삭제가 빈번하거나, 희소 그래프를 처리해야 한다면 리스트 기반.

---

결론

• 제공된 두 결과에서는 배열 기반 구현이 더 빠르고 메모리 효율적입니다.
• 하지만 문제에 따라 희소 그래프가 주어진다면 리스트 기반이 더 적합할 수 있습니다.
  즉, 그래프의 크기와 밀도를 고려하여 구현 방식을 선택해야 합니다.

 

그래프의 크기와 밀도를 고려하는 방법

---

밀집 그래프와 희소 그래프

그래프 알고리즘에서 **밀집 그래프(Dense Graph)**와 **희소 그래프(Sparse Graph)**는 그래프의 간선 개수를 기준으로 구분됩니다. 그래프를 효율적으로 표현하기 위해서는 그래프의 특성을 고려하여 적합한 자료구조를 선택해야 합니다.

---

1. 밀집 그래프 (Dense Graph)

정의

• 그래프의 간선 개수가 노드 수의 제곱에 가까운 그래프.
• 즉, 대부분의 노드 쌍이 서로 연결되어 있는 그래프를 의미.
• 간선의 개수 M≈ N^2 (여기서 N은 노드 수, M은 간선 수).

특징

• 거의 모든 노드가 서로 연결되어 있음.
• 간선이 많기 때문에 **인접 행렬(Adjacency Matrix)**로 표현하는 것이 적합.

장점: 인접 행렬

1. 빠른 간선 탐색:
   • 특정 두 노드 간에 간선이 존재하는지 O(1) 시간에 확인 가능.
2. 구현이 간단:
   • N×N 크기의 고정 배열을 사용하므로 구조가 직관적.

단점

• 메모리 사용량이 많음 O(N^2).
• 간선 추가/삭제가 O(1)로 빠르지만, 메모리 낭비가 심함.

---

2. 희소 그래프 (Sparse Graph)

정의

• 그래프의 간선 개수가 노드 수에 비례하거나 매우 적은 그래프.
• 즉, 대부분의 노드 쌍이 서로 연결되지 않은 그래프를 의미.
• 간선의 개수 M≪N^2.

특징

• 간선이 적기 때문에 **인접 리스트(Adjacency List)**로 표현하는 것이 적합.
• 소셜 네트워크, 도로 네트워크 등에서 자주 나타나는 그래프 유형.

장점: 인접 리스트

1. 메모리 효율성:
   • 연결된 간선만 저장하므로, 메모리 사용량이O(N + M)로 줄어듦.
   • M이 N^2에 비해 작을 경우 매우 유리.
2. 빠른 간선 추가/삭제:
   • 동적으로 간선을 관리할 수 있어 유연함.
3. 탐색 속도:
   • 특정 노드와 연결된 노드만 탐색하므로 BFS/DFS 시 불필요한 연산을 줄임.

단점

• 간선 존재 여부를 확인하려면 연결 리스트를 순회해야 하므로 O(Degree)가 필요.
• 구현이 상대적으로 복잡.

---

3. 밀집 그래프와 희소 그래프의 비교

기준 밀집 그래프 (Dense Graph) 희소 그래프 (Sparse Graph)

간선의 개수	M≈ N^2	M≪ N^2
그래프 표현	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
메모리 사용량	O(N2)	O(N+M)
탐색 시간	간선 존재 여부 확인: O(1)	간선 존재 여부 확인: O(Degree)
적합한 그래프	완전 그래프, 네트워크 라우터 등	도로 지도, 소셜 네트워크 등
구현 난이도	간단	복잡

---

4. 자료구조 선택 기준

밀집 그래프: 인접 행렬

• 장점:
  • 두 노드 간 간선 여부를 O(1)에 확인 가능.
  • 정해진 크기의 배열을 사용하므로 간결하고 직관적.
• 적합한 경우:
  • 간선이 매우 많은 밀집 그래프.
  • 예: 네트워크 라우터 연결, 완전 그래프 등.

희소 그래프: 인접 리스트

• 장점:
  • 메모리 효율적 (O(N+M).
  • BFS/DFS 탐색 시 불필요한 노드를 탐색하지 않음.
• 적합한 경우:
  • 간선이 적은 희소 그래프.
  • 예: 소셜 네트워크, 도로 지도, 트리 구조 등.

---

5. 사례

밀집 그래프의 예시

• 완전 그래프: N = 5

  그래프:
  1 → 2, 3, 4, 5
  2 → 1, 3, 4, 5
  3 → 1, 2, 4, 5
  4 → 1, 2, 3, 5
  5 → 1, 2, 3, 4
  

  • 인접 행렬:  
    • 인접 리스트에 비해 간선 확인이 빠름.

희소 그래프의 예시

• 도로 네트워크: N=5, M = 4

  그래프:
  1 → 2, 3
  2 → 1
  3 → 1, 4
  4 → 3
  5 → 없음
  

  • 인접 리스트:

    Node 1: 2 → 3
    Node 2: 1
    Node 3: 1 → 4
    Node 4: 3
    Node 5: 없음
    

  • 메모리 사용량이 인접 행렬에 비해 효율적.

---

6. 결론

그래프 알고리즘에서 밀집 그래프와 희소 그래프를 처리할 때, 적합한 자료구조를 선택하는 것은 성능에 큰 영향을 미칩니다.

• 밀집 그래프: 인접 행렬을 사용해 빠른 간선 확인과 간단한 구현을 추구.
• 희소 그래프: 인접 리스트를 사용해 메모리 효율성과 간선 탐색의 효율성을 확보.