alsgud3229   5년 전

처음에 컴파일 에러가 나와서 graph를 동적할당으로 바꾸어 줬습니다.

그 다음 제출하니 메모리초과가 뜨네요

혹시 무한루프를 돌때 처리를 안해서 생긴 문제일까요?

djm03178   5년 전

인접 행렬을 만드는 것 자체가 메모리 초과의 원인입니다. 4 * 10000 * 10000 = 약 400MB가 됩니다.

char로 1바이트 단위로 끊으면 범위 내에 들어오게 할 수는 있지만, 간선의 비율이 상대적으로 낮아 비효율적이고 시간 초과가 날 가능성이 높습니다.

그리고 malloc은 초기화를 해주지 않기 때문에 모두 0을 넣고 시작해야 합니다.

alsgud3229   5년 전

그렇다면 이렇게 큰 숫자에 대해서 풀때는 인접행렬말고 어떤식으로 풀어야할까요?

링크라도 좋습니다 !

djm03178   5년 전

연결된 간선들에 대한 정보만 저장해서 인접 리스트로 풀어야 합니다.

C라면 링크드 리스트가 제일 합리적일 것 같고, C++이라면 vector 등을 쓰는 것이 좋습니다.

alsgud3229   5년 전

고맙습니다

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