BFS에서 다음에 방문할 정점은 큐에 넣기 전에 방문체크를 하고 넣어야 합니다.
예를들어
지금 큐 안에 는1 ~ N이 담겨있고
1에서 x로 가는 길이 있고
2에서 x로 가는 길이 있고
...
N에서 x로 가는 길이 있을때
큐에서 1 ~ N을 순서대로 꺼내면서 다음에 방문할 정점을 큐에 넣는 작업을 하겠습니다.
22번 째 줄처럼 한다면 x는 딱 한 번만 들어갑니다.
하지만 17번째 줄처럼 코드를 짜면 x를 큐 안에 N번 넣게 됩니다.
이런 비효율적인 푸시를 계속 반복하면 메모리초과가 나기 쉽습니다.
rottoy 4년 전
bfs 코드로 맞고 다익스트라로 변환하는 과정에서 발생한 오류인데요
17번째 visited[a]=true를 저기 그대로 선언하면 메모리 초과가 납니다 ;;
22번째 줄 if (visited[to] == true)continue; 다음에 visited[to]=true로 선언하면 맞다고 나오는데 도대체 왜그러는걸까요..