동적 2차원 구조

Info

코딩테스트에서는 2차원 배열처럼 보이지만, 실제로는 행이나 열의 크기가 유동적인 경우가 많다.
이때는 int[][]보다 List<Integer>[], List<int[]>, List<List<Integer>>를 상황에 맞게 사용한다.

구조	상황	대표 예시
List<Integer>[]	행 고정, 열 가변	그래프, 트리, 인접 리스트
List<int[]>	열 고정, 행 가변	간선 목록, 좌표 목록, 구간 목록
List<List<Integer>>	행 가변, 열 가변	행과 열이 모두 유동적인 데이터

List<Integer>[]는 노드 수는 고정되어 있고, 각 노드마다 연결된 노드 수가 다를 때 사용한다.
그래프 인접 리스트에서 가장 많이 사용한다.

List<Integer>[] graph = new ArrayList[n + 1];
 
for (int i = 0; i <= n; i++) {
    graph[i] = new ArrayList<>();
}
 
graph[a].add(b);

List<int[]>는 한 줄의 데이터 개수는 고정인데, 전체 데이터 개수는 입력에 따라 달라질 때 사용한다.

List<int[]> edges = new ArrayList<>();
 
edges.add(new int[]{a, b});
edges.add(new int[]{x, y, cost});

List<List<Integer>>는 행과 열이 모두 유동적일 때 사용한다.

List<List<Integer>> list = new ArrayList<>();
 
for (int i = 0; i < n; i++) {
    list.add(new ArrayList<>());
}
 
list.get(a).add(b);

그래프 인접 리스트 문제에서는 보통 List<List<Integer>>보다 List<Integer>[]를 더 자주 쓴다.

---