komabomin   7년 전

인접행렬 만들고 bfs돌면서 큐에 넣기전에 parent라는 배열에 노드의 부모를 저장하도록 했습니다. 반례가 어떤게 있을까요??


gallopsys   7년 전

int 2차원 배열 100000x100000면 어마어마한 메모리양입니다... 인접 행렬을 사용하기 보다는 인접 리스트를 사용해 접근해보세요.


BFS를 돌 때도 방문했다는 걸 다음에 표시하지 말고, 방문하지 않은 점이 있다면 즉시 표시하시는 게 좋습니다. 저렇게 다음에 표시하면 Queue에 중복된 값이 들어갈 확률이 매우 높습니다...!

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