juhongkim2   7년 전

배열범위를 벗어난것 같지도 않고 무한루프를 도는것 같지도 않은데 런타임에러가 뜹니다

어디서 잘못된건지 좀 알려주세요ㅠㅠ

portableangel   7년 전

큐에 들어가는 원소의 개수가 최대 501*501개를 넘을 수가 있네요.
예를 들어 2*2 맵이
1 2
2 3
과 같이 생겼고, 맨 왼쪽 위의 칸(1,1) 에서 출발한다면
queue에 (1,1)을 push하고 시작 -> queue에 (1,2), (2,1)이 push됨 -> (1,2), (2,1) 각각에서 (2,2)를 push
도합 5개의 원소가 들어갑니다.

어떤 칸에 방문할 수 있는 경우의 수가 2회 이상이라면(위 예제에서의 2,2처럼), 해당 칸에서 방문할 수 있는 칸들도 모두 2번씩 방문될테고

이것이 누적되면 큐의 사이즈를 넘어가게 됩니다.

위 BFS의 아이디어를 이용해 '어떤 칸에 방문했을 때, 그 칸에서 시작하는 최장 경로의 길이' 를 담을 501*501 배열을 이용하여
DP를 하나 설계해 보세요

nisroeld99   7년 전

메모이제이션 공부해보고 풀어보세요 !

juhongkim2   7년 전

답변정말 감사합니다!

501*501짜리 배열로 dp사용했더니 ac나오네요

그런데 그럼 이 문제는 애초에 bfs로는 풀수가 없는 문제인가요?

nisroeld99   7년 전

네 n =500이라 안될것같습니다 

런타임에러 자체도 메모리 에러같네요 bfs에서 너무 많은 데이터를 queue에 넣은듯싶습니다. 

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