minhyeok5287   2년 전

문제들에서 BFS, DFS를 구현할 때 시간 복잡도는 어느정도 계산을 할 수 있을거 같은데 
recursion limit의 적절한 값을 어떻게 설정해주는 것인지 의문이 생겼습니다. 

혹시 간선의 개수가 200000만개 이기 때문에 10만개 이상의 재귀 제한을 걸어놓는 것인지 궁금합니다!! 

글 읽어주셔서 감사합니다. 

sdpr   2년 전

1. 대충 노드 개수보다 크게 한다.

2. 돌렸더니..

2-1. 성공했다 -> 와 AC!

2-2. 재귀스택에러 -> 에잉.. (0하나 더 붙여서 제출)

minhyeok5287   2년 전

감사합니다. 질문을 잊고 있었는데 답변을 달아주셨네요. 
궁금한 점이 있는데 노드보다 더 크게 재귀 스택이 발생할 수 있나요?? -> 저는 BFS, DFS 구현 단계에서는없을 거라고 판단했습니다.  혹시 이런 경우를 보신적이 있나요?? 

sdpr   2년 전

구현에 따라 노드+1개정도는 가능하다고 보지만.. 그걸 넘어서면 절대 발생하면 안된다고 생각합니다.

아니면, 사이클 판단하려면 보통 dfs가 노드 두 번씩 방문 할 수 있게 해주는데 그러면 최대 2N번정도 방문할 수도 있겠네요.

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