jinsj1   6년 전

스스로 해결을 못해, 질문 올립니다.

결과를 출력하는 방식은 d배열에 저장하는 것이 아닌

전역변수 ans 를 구간[?]이 끝나면 증가시키는 방식으로 진행했습니다.

(메모이제이션이랑 큰 차이가 없다고 생각합니다..)


일단 메모리 초과 라는건 queue에 문제가 있다는 것으로 해석해서

처음에 없던 bool chk도 적용해 보았으나, 결과는 바뀌지 않네요.


조언 부탁드립니다! 

djm03178   6년 전

chk는 방문 여부를 검사하는 변수인가요?

하지만, 처음에 chk[0][0][k] = true; 를 한 것 외에는 방문을 기록하는 곳이 보이지 않네요.

jinsj1   6년 전

@djm03178

말씀대로 큐의 문제는 언급하신 방법을 적용해 해결된 듯 합니다.

그럼에도 틀렸습니다 가 뜨는데

내부 로직의 문제점을 지적해주실 수 있나요?

djm03178   6년 전

if(a[nx][ny] == 1 || chk[nx][ny][cnt-1]) continue;
q.push({{nx,ny},0});

이 부분이 좀 의문이네요. 이 부분은 분명히 상하좌우로 움직이는 부분이죠? 그렇다면 이 방향으로 움직이는 데에 있어서 cnt를 소모할 필요는 없을텐데, cnt로 검사하는 게 맞지 않을까요?
그리고, push 할 때 왜 0으로 주셨나요? 앞으로 원숭이가 말처럼 움직일 수 있는 횟수가 cnt번이면, 상하좌우로 움직인 후에도 cnt 번 움직일 수 있어야 할 것 같은데요.

jinsj1   6년 전

@djm03178

날카로운 지적 감사드립니다!

틀린 부분이 한 두군데가 아니네요

일단, push 를 0으로 준건 더 이상 말처럼 이동을 할 수 없다는 것인데

k를 0으로 만든 다음 상하좌우로 이동하는 방식으로 구현했던 것 같아요(틀린 것이죠, k 가 0이 아니라도 상하좌우를 이동할 수 있고, 이때는 k 가 보존되니까요)


다른 블로그 살펴보니, (이전에는 찾아도 잘 안보였던ㅠㅠ)

말처럼 이동하는 경우에만 check 함수를 적용하는 것으로 구현하신 분도 있더라구요


지금의 코드는 오류 투성이라, 다시 심기일전해서 풀어봐야 할 것 같습니다

관심과 조언 감사드립니다!

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