2589번 보물섬 테스트케이스

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-B

해결된 질문

작성

351

수정됨

안녕하세요 큰돌 선생님 수업 잘 듣고있습니다.

다름이 아니라 강의를 듣기전 문제를 한번 풀어보았는데 궁금한 것이 생겨 질문 드리게 되었습니다.

https://www.acmicpc.net/source/55784974

육지인 지역 2곳을 뽑아서 bfs(최단거리)를 사용해 풀었는데요, 틀렸습니다. 시간복잡도의 문제도 있겠지만 그 전에 12%에서 반례 케이스가 존재하였습니다.

5 5

LLLLL

LWWWL

LLLLL

이 테스트케이스의 답은 8인데 저는 14가 나왔습니다.

궁금해서 visited배열을 출력하였더니,

이렇게 나왔습니다.

정상적으로 bfs가 수행되지않았는데 이유가 무엇인지 알 수 있을까요?

감사합니다!

c++코테 준비 같이 해요! 코딩-테스트 C++

답변 1

큰돌

지식공유자

안녕하세요 77님 ㅎㅎ

일단 이거 2곳이 아니라 1곳을 기반으로 해야 되는 것은 아시죠??

해당 설명은 제외하고 설명을 드리자면요.

자 이렇게 landList 에 넣었죠?

 if(a[i][j]=='L') landList.push_back({i,j});

근데?

        fill(&visited[0][0], &visited[0][0]+54*54,0);

        for(int j=0;j<i;j++){

            cnt=0;

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

            bfs(landList[i].first, landList[i].second);

이거요.

이렇게 하는게 맞는 코드 아닐까요?

    for(int i=0;i<landList.size();i++){
        fill(&visited[0][0], &visited[0][0]+54*54,0);
        tie(ey,ex)= landList[i]; 
        bfs(landList[i].first, landList[i].second);
        for(int j=0;j<i;j++){
            cnt=0;

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

goqlwj77

질문자

질문 답해주셔서 감사합니다~!! bfs는 출발점 하나만 필요한데 제가 개념을 착각했던거 같습니다! 감사합니다 😊

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

2589번 보물섬 테스트케이스