인접 리스트
공간 `O(V+E)`, 이웃 순회가 자연스럽습니다.
그래프 문제는 먼저 정점 V와 간선 E를 고정한 뒤 표현을 고른다
탐색 코드를 쓰기 전에 방향성, 가중치, 다중 간선, 입력 밀도를 결정해야 리스트/행렬 선택이 흔들리지 않습니다.
문제 대상을 그래프로 바꾸기
0
1
2
3
인접 행렬
간선 존재 확인이 `O(1)`이지만 공간은 `O(V^2)`입니다.
(to, weight)
최단 경로 문제라면 간선 타입을 처음부터 고정합니다.
핵심: 그래프 알고리즘 선택은 표현 선택 다음입니다. 모델이 틀리면 BFS/DFS/최단경로 코드도 같이 흔들립니다.