코딩테스트-인접리스트

인접 리스트(Adjacency List)를 이용한 그래프 표현과 DFS

인접행렬이 정점이 많아질수록 메모리를 O(V²)로 잡아먹는 반면, 인접 리스트는 실제 연결된 정점만 저장하기 때문에 메모리 효율이 훨씬 좋다. 실전 코딩 테스트에서 그래프는 대부분 인접 리스트로 푼다.

---

1. 인접 리스트란?

인접 리스트는 정점마다 "연결된 정점들"만 목록으로 저장하는 방식이다. 연결되지 않은 정점은 아예 저장하지 않으므로, 간선이 적은(희소) 그래프에서 메모리가 크게 절약된다.

---

2. 연결 리스트 vs 벡터

인접 리스트는 개념적으로는 연결 리스트(linked list)지만, 실제 구현에서는 벡터(vector)를 쓰는 것을 권장한다.

• 연결 리스트 : 삽입/삭제는 유리하지만, n번째 요소를 찾으려면 앞에서부터 따라가야 해 O(n)이 든다.
• 벡터 : 메모리가 연속적이라 n번째 요소를 O(1)에 바로 접근할 수 있고, 뒤에 삽입(push_back)도 평균 O(1)이라 순회·삽입 모두 유리하다.

상자 비유: 연결 리스트는 상자마다 "다음 상자 위치 쪽지"를 들고 하나씩 따라가야 하고, 벡터는 상자들이 한 줄로 붙어 있어 번호만 알면 바로 꺼낼 수 있다. 그래서 코딩 테스트 환경에서는 순회·참조가 빠른 벡터가 선호된다.

---

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[10];   // adj[u] = u와 연결된 정점 목록
int visited[10];

void go(int u) {
    visited[u] = 1;        // 방문 처리
    cout << u << "\n";

    for (int v : adj[u]) { // u와 연결된 정점만 순회
        if (visited[v] == 0) {
            go(v);
        }
    }
}

int main() {
    // 무방향 간선: 양쪽에 서로 추가
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[2].push_back(4);
    adj[4].push_back(2);

    // 방문 안 한 정점(간선이 있는)부터 탐색 → 모든 연결요소 방문
    for(int i = 0; i < 10; i++){
        if(adj[i].size() && visited[i] == 0){
            go(i);
        }
    }

    return 0;
}

인접행렬 코드와의 차이

• 인접행렬은 for(i = 0; i < V; i++)로 모든 정점을 확인하지만, 인접 리스트는 for(int v : adj[u])로 실제 연결된 정점만 순회한다.
• 덕분에 탐색이 연결의 수(간선 수)에 비례하므로 희소 그래프에서 훨씬 빠르다.
• 무방향 간선은 adj[a].push_back(b)와 adj[b].push_back(a)를 양쪽 모두 추가해야 한다.

---

4. 인접행렬 vs 인접 리스트 정리

기준	인접행렬	인접 리스트
메모리	O(V²)	O(V + E)
간선 존재 확인	O(1)	O(차수)
전체 탐색	O(V²)	O(V + E)
추천 상황	정점 적고 간선 촘촘할 때	대부분의 실전 문제 (희소 그래프)

---

정리

• 인접 리스트는 연결된 정점만 저장 → 메모리 O(V + E).
• 구현은 연결 리스트보다 벡터가 유리하다 (임의 접근 O(1), 순회·삽입 빠름).
• DFS 로직은 인접행렬과 동일하게 visited 배열로 중복 방문을 막는다.
• 실전에서는 경험상 대부분 인접 리스트로 푼다.