yousrain   4년 전

게시판 반례는 다 통과했습니다. 제출 시에

1) stl의 큐를 지역변수로 이용하여 bfs를 돌린 경우:

메모리 초과가 나옵니다

이 경우 20 x 20 반례에서 (원인은 모르겠지만) queue의 사이즈가 무한히 커지는 걸 확인했습니다.

다만, stl개념이 부족해서인지 이유는 잘 모르겠습니다...

2) 전역 또는 지역변수로 shark arr[10000]을 만들어서 내가만든 queue로 사용한 경우:

테스트케이스 및 게시판 반례는 전부 통과했습니다.

다만, 제출 시 런타임에러가 나는데 의심가는 게 선언한 사이즈를 넘어가는 인덱스를 접근했을 때라고 생각해서

배열의 크기를 1000만까지 늘려봤지만 결과는 똑같네요 ㅠㅠ

논리는 맞았다고 생각하는데 언어를 잘 모르는 부분에서 틀린 것 같아 질문 드립니다...

답변해주시면 감사하겠습니다.

rnjstpgns91   4년 전

작성하신 bfs논리 수정 안하고 통과되는 것으로 보아 논리가 틀리신건 아니고 tail이 범위 배열 벗어나는 경우가 있습니다.

왜 그런가 봤더니 중복이 너무 많아서 tail이 금방 끝까지 찬 것 같아요.

yousrain   4년 전

우선 답변 감사드려요!

중복을 피하려고

1) 방문한 경로는 visit맵을 이용해 true로 변경

2) tag값을 이용해 필요없는 추가를 막아주고

혹시몰라 arr크기를 천만까지 늘렸을 때도 런타임 에러가 뜬걸 보면 ㅠㅠ...

좀 더 코드를 보겠습니다!

rnjstpgns91   4년 전

잘 안보이신다면 간단하게 3x3 칸 그리시고 (2.2)에서 시작하셔서 작성하신 코드를 순서대로 따라가보시면 어디서 중복이 생겼는지 눈치 채실거 같아요

yousrain   4년 전

해결했습니다. 실행한 좌표의 visit를 true로 하지 않고 queue에 넣을 좌표를 true로 하니 중복 개수가 현저히 줄었네요 ㅠㅠ 내 코드에는 오류가 없을 거라는 자만이 결국 시간을 많이 잡아먹었습니다. 

지적 안해주셨으면 평생 몰랐을 것 같습니다  정말 감사합니다!!

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