[ps 팁] 그래프 순회는 무조건 인접 리스트로 구현하는 게 유리할까?

결론부터 먼저 말하면..

간선 리스트: MST 크루스칼 알고리즘

인접 행렬: 최단 거리 플로이드-와샬 알고리즘

인접 리스트: 그 외의 모든 것들!!

 

 

 

그냥 모든 ps 문제들은 인접 리스트로 구현하는 게 맞을까?

틀리다! 각각의 구현 방식들에는 장단점들이 분명해, 올바르게 선택해야 좋은 효율을 낼 수 있다.

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep5-1-%EA%B7%B8%EB%9E%98%ED%94%84graph

[알고리즘] ep5-1) 그래프(graph)

 

1. 인접 행렬(Adjacency Matrix): O(N^2)

인접 행렬은 정점 간의 연결 여부를 2차원 배열로 표현하는 방식이다. 정점이 N개일 때 N x N 크기의 배열을 만들어, graph[i][j]가 1이면 정점 i와 j가 연결되어 있음을 의미한다.

int N = 5; // 정점 수
int[][] graph = new int[N + 1][N + 1];

graph[1][2] = 1;
graph[2][1] = 1; // 양방향 간선

장점

• 두 정점이 연결되어 있는지 확인이 빠르다: O(1)
• 플로이드-워셜 알고리즘처럼 모든 정점 쌍을 탐색하는 알고리즘에 적합하다.

단점

• 메모리 낭비가 크다: 간선이 거의 없는 희소 그래프에서는 N^2 공간이 비효율적이다.
• 탐색 성능이 떨어진다: DFS나 BFS에서 모든 정점의 연결 여부를 매번 확인해야 하므로 O(N^2) 시간이 걸린다.

---

2. 인접 리스트(Adjacency List): O(N + M)

인접 리스트는 각 정점마다 연결된 정점들을 리스트 형태로 저장하는 방식이다. 공간을 간선 수 M만큼만 사용하므로, 보통의 코딩 테스트나 실전 문제에서는 인접 리스트를 사용하는 것이 일반적이다.

int N = 5; // 정점 수
List<Integer>[] graph = new ArrayList[N + 1];

for (int i = 1; i <= N; i++) {
    graph[i] = new ArrayList<>();
}

graph[1].add(2);
graph[2].add(1); // 양방향 간선

장점

• 공간 효율이 높다: O(N + M)만큼만 공간을 사용한다.
• 탐색 성능이 좋다: DFS, BFS 시 연결된 정점만 순회하면 되므로 O(N + M) 시간으로 동작한다.
• 정점 번호 오름차순 탐색도 쉽게 구현 가능하다: 각 리스트를 정렬하면 된다.

단점

• 두 정점 간의 연결 여부를 확인할 때는 O(리스트 길이)만큼 시간이 걸린다.

---

3. 간선 리스트(Edge List): O(M log N) (정렬 시)

간선 리스트는 모든 간선을 객체 또는 배열로 저장하는 방식이다. 간선의 출발점, 도착점, 가중치를 따로 관리할 수 있기 때문에 최소 신장 트리(MST) 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘 구현 시 주로 사용된다.

class Edge implements Comparable<Edge> {
    int from, to, weight;

    Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

List<Edge> edgeList = new ArrayList<>();
edgeList.add(new Edge(1, 2, 3));
edgeList.add(new Edge(1, 3, 1));

장점

• 간선 중심 알고리즘에 적합하다: 크루스칼 알고리즘처럼 간선을 정렬하여 사용하는 경우 유리하다.
• 메모리 사용이 효율적이다: 간선만 저장하므로 O(M)만 사용한다.

단점

• 정점 간 연결 여부를 빠르게 알 수 없다: 연결 여부를 확인하려면 모든 간선을 검색해야 한다.
• DFS, BFS처럼 인접 정점을 자주 탐색하는 문제에는 부적합하다.

---

그렇다면 실전 코딩테스트에서는?

실제 코딩테스트 문제에서는 다음과 같은 선택 기준을 가지고 접근하면 된다:

• 그래프 탐색(DFS, BFS) 문제 → 기본적으로 인접 리스트를 사용하는 것이 좋다.
• 모든 정점 쌍의 연결 여부나 경로 비용 계산이 필요하다면 → 인접 행렬도 고려해볼 수 있다. (예: 플로이드-와샬)
• 최소 신장 트리(MST) 문제에서 크루스칼 알고리즘을 쓴다면 → 간선 리스트 사용이 가장 적절하다.

 

 

 

 

(최종 정리표)