안녕하세요 큰돌 선생님 수업 잘 듣고있습니다.다름이 아니라 강의를 듣기전 문제를 한번 풀어보았는데 궁금한 것이 생겨 질문 드리게 되었습니다.<a target="_blank" rel="noopener noreferrer nofollow" href="https://www.acmicpc.net/source/55784974">https://www.acmicpc.net/source/55784974</a>육지인 지역 2곳을 뽑아서 bfs(최단거리)를 사용해 풀었는데요, 틀렸습니다. 시간복잡도의 문제도 있겠지만 그 전에 12%에서 반례 케이스가 존재하였습니다.5 5LLLLLLWWWLLWWWLLWWWLLLLLL이 테스트케이스의 답은 8인데 저는 14가 나왔습니다.궁금해서 visited배열을 출력하였더니, <img src="https://cdn.inflearn.com/public/files/posts/cc54ddff-db34-47e5-baa9-8ccaea3f77b9/image.png">&nbsp;이렇게 나왔습니다.정상적으로 bfs가 수행되지않았는데 이유가 무엇인지 알 수 있을까요?감사합니다!

안녕하세요 77님 ㅎㅎ일단 이거 2곳이 아니라 1곳을 기반으로 해야 되는 것은 아시죠??해당 설명은 제외하고 설명을 드리자면요.자 이렇게 landList 에 넣었죠?<pre class="hljs"><code> if(a[i][j]=='L') landList.push_back({i,j});</code></pre>&nbsp;근데?<pre class="hljs"><code> fill(&amp;visited[0][0], &amp;visited[0][0]+54*54,0);

 for(int j=0;j&lt;i;j++){

 cnt=0;

 tie(ey,ex)= landList[j];

 bfs(landList[i].first, landList[i].second); </code></pre>이거요. 이렇게 하는게 맞는 코드 아닐까요?<pre class="hljs"><code> for(int i=0;i&lt;landList.size();i++){
 fill(&amp;visited[0][0], &amp;visited[0][0]+54*54,0);
 tie(ey,ex)= landList[i]; 
 bfs(landList[i].first, landList[i].second);
 for(int j=0;j&lt;i;j++){
 cnt=0; </code></pre>&nbsp;또 질문 있으시면 언제든지 질문 부탁드립니다.좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)감사합니다.강사 큰돌 올림.

인프런 커뮤니티 질문&답변

2589번 보물섬 테스트케이스