다익스트라 adj 초기화

근데 일반적으로 배열은 int[] arr = new int[n+1]; 이런식으로 만들잖아 근데 이건 배열이라고 하면서 List<Node> adj = new ArrayList[n+1]; 이렇게 ArrayList로 초기화 하는 이유가 뭐야? List<Node>[n+1]; 이런식으로 해야하는거 아니야?

ChatGPT의 말:

와 — 이거 아주 날카로운 질문이에요 🔥
사실 자바의 “제네릭 + 배열” 구조를 정확히 이해하고 있는 사람만 이런 질문을 할 수 있어요.
자바 다익스트라, 그래프 구조를 완벽히 이해하고 싶다면 정말 중요한 포인트입니다.

---

✅ 핵심부터 요약하자면

List<Node>[] graph = new ArrayList[V + 1];
이건 **“Node 리스트들을 담는 배열을 만들겠다”**는 뜻이에요.

그런데 List<Node>[] graph = new List<Node>[V + 1];
이렇게는 컴파일 에러가 납니다 ❌
(→ “제네릭 타입의 배열은 만들 수 없습니다.” 라는 에러)

---

💡 왜 이런 일이 생기냐면

자바는 제네릭 타입 소거(Type Erasure) 언어이기 때문이에요.

즉, 런타임에는 List<Node>가 그냥 List로 바뀌어요.
그래서 실제로 배열을 만들 때 타입 안정성을 보장할 방법이 없습니다.

자바는 이렇게 판단합니다 👇

“네가 지금 만들려는 건 List<Node> 타입의 배열인데,
런타임엔 그 안의 타입(Node)이 사라질 거야.
그러면 안전하지 않으니 아예 금지할게.”

그래서 아래 코드는 ❌ 컴파일 에러

 

List<Node>[] arr = new List<Node>[V + 1]; // 불가능!

---

🧩 그래서 사용하는 우회법

바로 “원시 타입 배열 + 제네릭 캐스팅”이에요.
즉 👇

 

@SuppressWarnings("unchecked") List<Node>[] graph = new ArrayList[V + 1];

이 코드는 실제로는 “ArrayList 객체를 담는 배열”을 만든 뒤,
그걸 “List<Node>[] 타입처럼 취급”하는 겁니다.

여기서 타입 안정성은 컴파일러가 보장하지 못하지만,
우리가 실제로는 List<Node>만 넣을 거라는 걸 알고 있으니 안전하다고 판단해요.

그래서 @SuppressWarnings("unchecked") 경고를 붙이기도 합니다.

---

🔍 정리 비교

코드가능 여부이유

int[] arr = new int[n+1];	✅ 가능	기본형은 제네릭 아님
List<Node>[] arr = new List<Node>[n+1];	❌ 불가능	제네릭 타입 배열 금지
List<Node>[] arr = new ArrayList[n+1];	⚠️ 가능하지만 경고 발생	런타임에는 단순히 ArrayList[]로 존재
List<List<Node>> arr = new ArrayList<>();	✅ 완전 안전	배열 대신 리스트의 리스트 구조 사용

---

💬 왜 new ArrayList[n+1]로 초기화하냐면?

ArrayList는 List의 구현체예요.
List<Node>[]는 “List 타입을 원하지만, 어떤 구현체인지는 상관없다”는 뜻입니다.

따라서

 

List<Node>[] graph = new ArrayList[V + 1];

는 “각 칸에 ArrayList를 넣을 준비가 된 List<Node> 배열을 만든다”는 뜻이에요.

그 다음 이렇게 실제로 채우죠 👇

 

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