whdvy3   5달 전

어느부분에서 시간초과가 발생하는것일까요..제가 찾아봤을때는 도저히 시간초과가 발생할만한 부분이 없는거같아서 이렇게 질문올립니다..ㅠ

bamgoesn   5달 전

현재 코드는 깊이 5의 DFS를 돌리고 있습니다. 이때 시작점은 방문하지 않았다고 체크하고 있고, _sum에서 시작점의 값을 포함하고 있지 않습니다.

50행의 DFS 호출에서 _depth=0, _sum=0부터 시작해, _depth가 4가 될 때까지 "새로 이동한 칸의 값"을 _sum에 포함하여 DFS를 돌리고 있습니다. _depth가 0부터 4까지 올라가며 재귀호출이 일어나므로 재귀의 깊이는 5이며, _sum이 0부터 시작하면서 _sum에 arr[nx][ny]를 더하므로 시작점의 값은 _sum에 포함되지 않게 됩니다.

한편 DFS의 깊이를 5로 돌리면서 시작점은 제외하기 때문에 답은 맞게 나옵니다.

때문에 각 테트로미노의 경우가 너무 많이 중복되어 계산됩니다. 실제로 이 그래프는 거의 모든 노드의 차수가 4로 상당히 조밀합니다. 따라서 DFS의 깊이가 늘어날수록 소요시간은 지수적으로 늘어납니다.

시작점을 _sum에 포함시키고, DFS의 깊이를 4로 줄여보세요.

bamgoesn   5달 전

추가로, Swift에선 재귀함수의 호출이 매우 느린 것 같다고 들은 바가 있습니다. 실제로 재귀함수 호출이 느린 것인지, BOJ의 컴파일러가 이상한 것인지는 잘 모르겠습니다만 함수의 호출 오버헤드가 매우 큰 건지 재귀함수가 굉장히 느립니다.

정확히 같은 논리의 코드를 다른 자주 쓰이는 언어로 제출해보면 깊이 5의 재귀, 즉 질문자님과 동일한 로직으로 작성한 코드가 여유있게 통과됩니다. 이 점 참고하시기 바랍니다.

whdvy3   5달 전

감사합니다 ㅠㅠ 논리는 맞는데 언어로인해 제약받는 부분이 많은것 같네요.. 감사합니다!!

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