specimen   5년 전

테스트 케이스를 하나로 했을 때는 답이 잘 나오는데

문제에서 제시한 예제를 복붙을 했을 때는 답이 이상하게 나옵니다.. 

음.. 어디서 뭔가 값이 변경된거 같긴 한데 계속 봐도 잘 모르겠네요..

djm03178   5년 전

18번째 줄의 break에 의해서 큐에 원소가 남아있는데도 탐색을 종료할 수 있고, 이 원소는 다음 케이스 때 사용됩니다.

9번째 줄을 11번째 줄로 옮기면 됩니다.

specimen   5년 전

답변 정말 감사드립니다. 옮겨서 맞긴 했는데 죄송하지만 이유를 상세하게 설명해주실 수 있으신가요? ㅠㅠ 부탁드립니다.

djm03178   5년 전

큐에는 원소가 하나 들어가고 하나 나오고가 반복되는 것이 아니고, 한 번에 여러 개의 원소가 들어갈 수 있습니다. 그래서 어떤 시점에 큐에 담겨있는 원소가 여럿일 수 있는데, 이 때 나온 원소가 끝 좌표라면 18번째 줄에 의해서 바로 break되어 루프를 탈출하게 됩니다. 그런데 아직 큐에는 여러 원소들이 남아있습니다.

다음 케이스가 되어 다시 bfs 함수에 들어왔을 때도 여전히 그 원소들은 남아있고, 12번째 줄이 새로운 시작점을 좌표에 넣으면 그 원소가 루프에서 바로 나오는 것이 아니라 이전 케이스에 큐에 들어갔던 원소들이 먼저 나오게 됩니다. 반면에 큐를 지역 변수로 선언하게 되면 bfs 함수가 종료되는 순간 큐도 같이 사라지고, 다음 케이스에서는 새로운 큐가 만들어지므로 이런 문제가 없게 됩니다.

specimen   5년 전

음 결론은 큐에 한 번에 여러개의 원소가 들어갈 수 있기 때문에 전역변수로 선언할 때, 큐안에 원소들이 남을 수도 있다네요? 

뭔가 잘 와닿지가 않네요.. 어쨌든 큐에 push를 하는건 처음 함수 시작 부분과 조건이 맞을 시에 하기로 되어 있는데 여러 개의 값이 큐에 들어가면 정답이 안나올 수도 있는거 아닌가요? 

djm03178   5년 전

문제에 주어진 예시 그림을 봅시다.

afcb460c-9735-40e4-ad64-76228a00f648

시작점이 가운데칸이면, 무려 8개의 칸을 19번째 줄의 for 루프를 돌면서 큐에 차례대로 push하게 됩니다. 그러면 이 순간에는 큐에 8개의 원소가 들어가 있겠네요.

만약 바로 다음 번에 큐에서 나온 원소가 끝점이라면, 큐에는 7개의 원소가 남은 상태에서 break를 하게 되겠죠. 나머지 7개 원소들은 어떻게 되나요? 다음 케이스로 넘어가게 됩니다.

specimen   5년 전

와 대박 감사합니다. 한번에 이해가 갔습니다. 기존에 풀었던 문제들을 보니 다 테스트 케이스를 여러번 돌리는게 아니었더군요. 아니면 우연히 제가 그 문제를 풀때 그 문제에서는 지역변수로 선언한걸 수도 있구요. 

그러면 정리하자면 여러 개의 테스트를 한번에 돌리는 문제는 큐를 다음 케이스로 들어가기전 초기화를 해주거나 지역변수로 선언을 하면 되겠군요.

fbfbf1   3년 전

저도 이거 궁금했는데

아주 명확한 답변이네요

1년 전 글이지만 감사합니다

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