scream2004   4년 전

50% 정도에서 실패가 뜨는데 어떤 실수가있는지 모르겠습니다.

배추 정보를 list에 담아서 bfs하는데 이미 거쳐간 배추의 경우 list에서 빼버리게 코드를 짰습니다.

그리고 인접배추를 구할때 x차이가 1이거나 y차이가 1일때 인접배추라고 판단하게 코드가 짜여있습니다.

마지막으로 큐에 아무것도 없을때 (인근 배추 연결됐다고 판단) result ++하게 되어있습니다

무엇을 놓치고 있을까요?

다른 분들 코드 보니  M,N을 사용하는데 저는 사용하지 않아서 싹다 갈아 엎어야하나 고민입니다..

djm03178   4년 전

44번째 줄이 실행되는 순간 j번째 이후의 원소들이 전부 한 칸씩 앞으로 당겨져 j+1번째가 j번째가 되므로 그 다음 루프에서도 j번째 원소를 다시 확인해야 하는데, j가 증가되어 j+1이 되므로 확인하지 못하게 됩니다.

scream2004   4년 전

댓글감사합니다 혹시 말씀하신 부분을 

while(!queue.isEmpty()) 

 { bachu poll=queue.poll(); 

         int q=list.size();   <<<<<<<<<<<여기랑

         for(int j=0; j < q; j++)

             { if(Math.abs(list.get(j).x - poll.x)+Math.abs(list.get(j).y - poll.y)==1) 

                { 

                    queue.offer(list.get(j)); 

                    list.remove(list.get(j)); 

                    j=0; q=list.size();             <<<<<<<<<<<<<<<<이부분 수정했습니다

           } } }

리스트나간후에  for문을 다시 처음부터 돌게끔 수정해봤는데도 실패가 뜨네요 

수정한대로 코드가 돌아가면 놓치는 부분은 없지 않을까요? 

그래도 똑같은 부분에서 실패가 뜨네요 ..


scream2004   4년 전

방금 올린 댓글 부분을

       j=0; q=list.size()  대신 j-- ; q--; 로 수정했더니 해결되었습니다

하지만 이 둘의 차이가 무엇인지 잘 모르겠습니다 ㅠ.ㅠ

후자의 경우 나간부분부터 감안하여서 j, q를 수정해서 돌아가는건 알겠는데

전자의 경우 remove한 이후로 다시 처음부터 도는거라 시간은 더 오래걸려도 결국 같은 코드가 아닌가요??

djm03178   4년 전

0번째 원소가 지워지고 j를 다시 0으로 설정하면, 루프를 돌아 증감문이 실행될 때 j는 1이 됩니다. 0번째를 건너뛰게 됩니다. j--로 하면 j가 -1이 되었다가 0이 되기 때문에 0번째를 다시 체크할 수 있습니다.

scream2004   4년 전

아 .. 그거를 생각못했네요

감사합니다__

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