algospot.com :: 질문과 답변: 그래프 구현 관련 질문 드립니다.

그래프 구현 관련 질문 드립니다.

wookayin

vector 로 adjacent list 를 관리하시면 됩니다. jmbook 에 관련 코드가 있으니 한번 살펴보세요~

8년 전 link
wookayin

동적할당 이용하여 그래프를 구성하는거 자체가 시간이 오래걸리게 하지는 않습니다. 다익스트라 구현할때는 어떤 edge가 존재하는지를 찾을 필요는 없으므로 말씀하신 탐색은 필요 없고 (아마 이거때문에 TLE 나는것 같지만) 그냥 구성한 list를 순회하기만 하면 될거에요..

8년 전 link
chochogogo

ㅜㅜ
c사용자라...ㅜㅜ백터는....
다른 cpp 패스한 사람 코드에서 그래프 구현부만 c 동적할당으로 바꾸었는데
tle나더라구요...
찾아보니 동적할당이 메모리 재배치 때문에 시간이 오래 걸린다는 이야기가
있어서 다른 방법을 찾고 있습니다ㅜㅜ

8년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

안녕하세요?
그래프 구현 관련 질문 드립니다.

다익스트라 알고리즘을 구현하는 문제가 있었습니다.

인풋으로 엣지 정보가 주어졌는데
2차원 배열을 이용하여 인접 행렬이나 인접 리스트를
이용해 그래프를 구현하면 메모리 사이즈가 문제에서
요구하는 메모리를 넘어가는 상황입니다.

이를 해결하기 위해 동적 할당 이용하여 그래프를 구성하였는데,
이번에는 Time Out이 발생하였습니다.

이상황에서 그래프를 구현, 다익스트라 알고리즘을 구현하는 좋은 방법이 있는지 여쭙니다.

제가 생각한 방법은 엣지 정보를 정점 기준 정렬하고,
이진 탐색을 이용하여 방문하고자 하는 노드를 찾는 방법을
생각해 보았는데, 다른 좋은 방법이 있을까요??

8년 전