11725번 - 트리의 부모 찾기
인접행렬 만들고 bfs돌면서 큐에 넣기전에 parent라는 배열에 노드의 부모를 저장하도록 했습니다. 반례가 어떤게 있을까요??
int 2차원 배열 100000x100000면 어마어마한 메모리양입니다... 인접 행렬을 사용하기 보다는 인접 리스트를 사용해 접근해보세요.
BFS를 돌 때도 방문했다는 걸 다음에 표시하지 말고, 방문하지 않은 점이 있다면 즉시 표시하시는 게 좋습니다. 저렇게 다음에 표시하면 Queue에 중복된 값이 들어갈 확률이 매우 높습니다...!
댓글을 작성하려면 로그인해야 합니다.
komabomin 7년 전
인접행렬 만들고 bfs돌면서 큐에 넣기전에 parent라는 배열에 노드의 부모를 저장하도록 했습니다. 반례가 어떤게 있을까요??