rottoy   4년 전

bfs 코드로 맞고 다익스트라로 변환하는 과정에서 발생한 오류인데요

17번째 visited[a]=true를 저기 그대로 선언하면 메모리 초과가 납니다 ;;

22번째 줄 if (visited[to] == true)continue; 다음에 visited[to]=true로 선언하면 맞다고 나오는데 도대체 왜그러는걸까요..

palilo   4년 전

BFS에서 다음에 방문할 정점은 큐에 넣기 전에 방문체크를 하고 넣어야 합니다.

예를들어

지금 큐 안에 는1 ~ N이 담겨있고

1에서 x로 가는 길이 있고

2에서 x로 가는 길이 있고

...

N에서 x로 가는 길이 있을때

큐에서 1 ~ N을 순서대로 꺼내면서 다음에 방문할 정점을 큐에 넣는 작업을 하겠습니다.

22번 째 줄처럼 한다면 x는 딱 한 번만 들어갑니다.

하지만 17번째 줄처럼 코드를 짜면 x를 큐 안에 N번 넣게 됩니다.

이런 비효율적인 푸시를 계속 반복하면 메모리초과가 나기 쉽습니다.

rottoy   4년 전

아하 둘이 같은건줄 알았는데 전혀 다른 구조였군요... 감사합니다.

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