khy0419   5년 전


1939문제에서 힌트로 이분탐색이라고 나와 있지만, bfs만을 이용해서 풀고 있습니다.

처음 문제 풀시에 배열의 크기를 [ 10,000 ][ 10,000 ]로 잡고 해서 메모리 초과가 나

모두 malloc을 이용한 동적 할당을 사용했습니다.

맵 정보는 bfs가 진행될때마다 갱신된 맵 정보를 넘겨주는 방식으로 했습니다.

중간에 주석처리된 free(tmp_map)를 했을 경우 제대로된 탐색을 하지 않아 해제를 하지 않고 진행중인데 메모리 초과가 나고 있습니다.

그래서 원인이 이쪽 부분이 아닌지 추측을 하고 있습니다.

어떻게 해결하는 것이 좋을까요?

djm03178   5년 전

[10000][10000]을 할당하는 것이나 malloc으로 10000칸씩 10000줄을 동적할당하는 것이나 근본적으로는 같은 이야기입니다. 메모리 초과가 나는 것이 당연합니다.

이렇게 정점의 수가 많고 간선의 수가 V^2에 한참 못 미치는 문제에서는 인접 행렬이 아니라 인접 리스트를 통해 해결하는 것이 바람직합니다.

byjun3992   4년 전

이거 이분탐색으로 중량제한 하지 않으면 큐가 터집니다... 속도도안나오고

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