zhoang3   2년 전

런타임에러 설명좀 부탁드립니다...

chogahui05   2년 전

인덱스 범위를 벗어나면 런타임 에러가 뜨겠네요.

인접 리스트로 구현을 안 하고, 인접 행렬로 구현하신 거 같은데요.

정점의 갯수가 V라면, 인접 행렬로 구현하실 경우 공간 복잡도가 V^2가 되겠죠?


그런데 V = 2만이네요. 2만 * 2만 = 4억. inp 배열의 크기가 4억 * sizeof(int)네요.

64bit라 가정하면 대충 32억 byte가 되겠는데요? 런타임 에러가 안 걸려도

계산 과정에서 시간 초과 먹겠네요.

chogahui05   2년 전

일단 이 문제 같은 경우, 정점의 갯수는 최대 2만개고요.

path의 갯수가 최대 30만개네요.

행렬로 표현했을 때, 4억이네요. 그리고 인접 리스트로 표현한 경우, 최대 30만..


30만 / 4억 = 약 3/4000인가요?

only C로 구현하시려면 희소 행렬을 구현하셔야 합니다.

java는 Map을 써 주시면 되는데.. key값으로 무엇을 넣으면 좋을 지는 잘 생각해 보세요.


나머지 과정은, 생략하도록 할게요.

솔직히 질답게 보면 바로 나오긴 하지만, 쉽게 알려주면 넘넘 시시하잖아요.

댓글을 작성하려면 로그인해야 합니다.