16928번 - 뱀과 사다리 게임
이 문제를 BFS와 재귀로 풀었습니다.
BFS로는 정답을 맞았는데
재귀로 구현하니까 스택 오버플로우가 납니다..
두 코드의 동작이 동일하다고 생각하는데 왜 그런지 모르겠습니다.
놓치고 있는 부분 알려주시면 감사하겠습니다.
스택 오버플로우가 나는 버전
배열에서 [100] 에 해당하는 값을 사용하려면 배열의 크기는 101 이상이여야합니다.
현재 코드는 nCur값이 100이거나, i+cur 값이 100 이상이 될 때 배열 값의 범위를 넘겨서 이상한 동작을 하게 됩니다.
즉, 첫번째 bfs 코드도 틀리게 나올 가능성이 있는 코드인데 우연찮게 맞은것 뿐입니다
추가적으로, 무한루프가 발생하는 경우, 해당 코드도 덩달아 무한루프에 빠지게 됩니다.
BFS로 잘못 구현한 코드를 수정했습니다.
index 100에 접근하지 않도록 처리했습니다. 정답처리가 떴습니다.
헌데, 34줄~39줄을 아래와 같이 바꾸면
if (nCur == 100) {
ret = min(ret, nCnt);
continue;
}
런타임 에러가 발생합니다. 이는 사다리를 탔을때 100을 초과하는 경우가 있어서 그런것인가요?
그리고 재귀 버전도 조언주신대로 수정했는데, 런타임 에러가 발생합니다.
문제에 대한 제 접근 방식 자체가 잘못된건가요?
댓글을 작성하려면 로그인해야 합니다.
bbwwpark 3년 전
이 문제를 BFS와 재귀로 풀었습니다.
BFS로는 정답을 맞았는데
재귀로 구현하니까 스택 오버플로우가 납니다..
두 코드의 동작이 동일하다고 생각하는데 왜 그런지 모르겠습니다.
놓치고 있는 부분 알려주시면 감사하겠습니다.