[Algorithm] 인접 리스트(Adjacency List) 정리

04 Jan 2025 in Algorithm

트리, 그래프 문제에서 자주 사용하는 인접 리스트 구조를 정리했습니다.

그래프 문제를 풀다 보면 “왜 인접 행렬 말고 인접 리스트를 쓰는지”, “List<int[]>[] 이 구조가 왜 이렇게 생겼는지” 헷갈릴 때가 많다.

이 글에서는 코테 기준으로 딱 필요한 만큼만 정리한다.

---

🌳 인접 리스트란?

각 정점이 연결된 정점들만 리스트로 가지고 있는 구조

✔️ 왜 쓰나?

• 노드 ≤ 10,000 이상일 때
• 간선 수가 많지 않은 그래프 (트리 포함)
• 메모리 효율 + 탐색 효율이 좋음

---

📌 인접 행렬 vs 인접 리스트

구분	인접 행렬	인접 리스트
구조	int[N][N]	List<Edge>[]
메모리	O(N²)	O(N + E)
간선 확인	빠름	느림
DFS/BFS	불리	유리 (코테 표준)
트리 문제	❌	⭕

👉 트리 / BFS / DFS / 지름 문제 = 인접 리스트

---

🧱 기본 구조 (가장 중요)

1️⃣ 선언

List<int[]>[] graph;

• graph[i] : i번 노드와 연결된 모든 간선 목록
• int[] : {다음 노드, 가중치}

---

2️⃣ 초기화 (절대 빠지면 안 됨)

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

❗ 이거 안 하면 NullPointerException 100% 발생

---

3️⃣ 간선 입력 (무방향 그래프 / 트리)

graph[u].add(new int[]{v, w});
graph[v].add(new int[]{u, w});

• 트리는 무방향 그래프
• 부모 → 자식만 넣으면 ❌ (DFS에서 못 돌아옴)

---

🔍 실제 예시 (트리)

입력:

1 - 2 (3)
1 - 3 (2)

구조:

graph[1] → [ [2,3], [3,2] ]
graph[2] → [ [1,3] ]
graph[3] → [ [1,2] ]

---

🚶 DFS / BFS에서 사용하는 방법

DFS 예시

void dfs(int cur, int dist) {
    visited[cur] = true;

    for (int[] next : graph[cur]) {
        int to = next[0];
        int w  = next[1];

        if (!visited[to]) {
            dfs(to, dist + w);
        }
    }
}

핵심 포인트

• graph[cur] = 현재 노드와 연결된 모든 간선
• next[0] = 다음 노드
• next[1] = 가중치

---

🚨 자주 터지는 실수 TOP 5

❌ 1. graph 배열만 만들고 내부 리스트 안 만듦

graph = new ArrayList[n+1]; // ❌

→ 반드시 for문으로 new ArrayList<>()

---

❌ 2. 무방향인데 한쪽만 추가

graph[u].add(v); // ❌

---

❌ 3. visited 크기 미초기화

static boolean[] visited = new boolean[n+1]; // ❌

→ n 입력 전이라 크기 0

---

❌ 4. farNode = 0 인 상태로 DFS

→ graph[0] 접근 → NPE

---

❌ 5. DFS 깊이 너무 깊음 (StackOverflow)

• 노드 10,000
• 일자 트리

👉 이 경우 BFS가 더 안전

---

🧠 언제 인접 리스트를 쓰나?

문제 유형	사용 여부
트리의 지름	⭐⭐⭐⭐⭐
BFS / DFS	⭐⭐⭐⭐⭐
다익스트라	⭐⭐⭐⭐⭐
플로이드 워셜	❌
완전 그래프	❌

---

📘 대표 문제

문제	이유
트리의 지름	2번 DFS
숨바꼭질	BFS
네트워크	DFS/BFS
치킨 배달	좌표 + 리스트
DSLR	상태 그래프

---

✨ 한 줄 요약

인접 리스트 = “각 노드가 연결된 노드만 들고 있는 구조” 트리·BFS·DFS 문제에서는 거의 무조건 이걸 쓴다

---