zipbob   9달 전

bfs 비슷하게 구현하는데
depth? 를 어떤식으로 구해야될지 잘 모르겠습니다. (얼마나 뻗어나갔는지(즉 정답;;)) 
현재는 
pair 구현하니까  메모리 초과 뜨네요
좋은 방법 알려주시면 감사하겠습니다.

indioindio   9달 전

음 좋은 방법인지는 모르겠지만 저는 f(src, dst, cnt)

로 해서 src에서 갈 수 있는 곳을 nxt에 넣는 과정에서 dst가 있으면 cnt를 반환하고 아니면

재귀호출로 f(nxt, dst, cnt+1)를 호출하여 주로 풉니다.

wow1514   9달 전

위 코드로 보면 중복된 위치도 계속해서 탐색하는것 같네요. 중복해서 계속 큐에 들어가니 큐가 점점 쌓이고 결국 메모리 초과 뜨는게 아닌가 생각합니다.

배열 변수 하나 만들어서 한번 탐색했던곳은 다시 탐색안하도록 해주는게 좋을 것 같습니다.

wow1514   9달 전

문제 예제를 생각해보면

현재 위치는 5, 가야하는 곳은 17.

첫 while에서 큐에 4,6,10이 들어가고 두번째 루프에는 6,10,3,5,8 이런식으로 들어가는것 같습니다.

즉 처음 들어갔던 5가 또들어가니 4,6,10도 다시들어갈꺼고 방문하는 위치가 늘어나면 늘어날 수록 큐에 들어가는 아이템 수도 증가합니다.

n크기가 100000인데 위 방법대로라면 0이 하나 더 들어간 배열을 만들어도 공간이 모자랄거 같네요.

zipbob   9달 전

답변 감사합니다 

근데 아직 해결은 못했네요 ㅠㅠ

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