500 * 2,500 = 1,250,000인 경우 인접 리스트로 구현할 때 LinkedList 혹은 ArrayList로 많이 구현합니다.
int[][]의 경우 구조가 단순하고 객체 헤더, 참조, 배열 헤더만 신경쓰면 되기 때문에 1,250,000회인 경우 대략 23[MB} 정도 나와 AC 판정을 받을 수 있습니다.
반면 map의 경우 해시 버킷 + 엔트리(Node) + 키(Integer 객체) + 리스트(ArrayList 객체) + 엣지(Edge 객체) 등 다층 객체 오버헤드를 잔뜩 끌고 와서 메모리가 급격히 커집니다.
거기에 map의 각 key마다 value가 계속 증가하고 key의 수도 적지 않기 때문에 128[MB]는 그냥 훌쩍 뛰어넘습니다.
map을 주로 사용하는 경우는 key와 value가 1대1 대응할 때 map이 더 효율적입니다.
Javascript로 비유하면 객체(속성들의 모임), Python으로 비유하면 사전(dictionary)에 해당하고 이들이 활용하는 문제들을 보면 주로 key와 value가 각각 하나씩 일대일 관계를 맺는 것을 알 수 있습니다.
하나의 key에 2개 이상의 value가 올 수도 있으나 하나의 key에 대한 value list의 크기가 고정되어 있습니다.

rud15dns 1년 전
안녕하세요!
벨만-포드 알고리즘을 구현하는 과정에서 메모리 초과가 발생하여 궁금한 점이 생겼습니다.
제가 생각하기에는 N개의 정점 중 실제로 존재하는 정점만 배열에 저장하면 불필요한 메모리를 줄일 수 있을 것 같아서, Map을 사용해 존재하는 정점과 간선만 저장하도록 구현했습니다.
그런데 오히려 Map을 사용했을 때 메모리 초과가 발생했습니다.
Sparse한 정점 구조를 가진 경우에는 Map이 배열보다 메모리를 절약할 수 있을 것이라고 생각했는데, 실제로는 왜 Map을 사용했을 때 메모리 초과가 나는지 궁금합니다.
제가 어떤 방식으로 초기화를 각각 했는지 아래 코드를 같이 첨부합니다.