cirly   6년 전

음.. 죄송합니다 코드가 조금 복잡하게 됬습니다. 

제가 구현해보려고 한 부분을 조금 설명드리겠습니다. 

일반적인 bfs로 구현 할 수 도 있지만, 조금 더 생각해서 시작점인 부분을 반도로 설정해 chkpenninsula 함수를 이용해 삼면이 바다일경우 bfs를 돌리고 그부분만 찾아서 bfs를 덜돌려 조금 효율적이지 않을까 생각해서 구현했지만 생각보다 반례가 많더라고요. 

예시:

5 7
WLLWWWL      WWWWWWWWW    0560001
LLLWLLL      WLLLWLLLW    3450432
LWLWLWW   => WLWLWLWWW => 2060500 
LWLWLLL      WLWLWLLLW    1070678
WLLWLWW      WWLLWLWWW    0980700
             WWWWWWWWW
생각한 반례: 반도가 없는 섬일경우
2 5    이 경우 반도설정을 2번째 섬일 경우밖에 못한다 혹은 2 2
LLLWL                                                  LL
LLLWL                                                  LL  이 경우도 반도가 없다 

그래서 고려해서 다시한번 cntIsland로 섬의 개수를 설정후 다시 한번 bfs를 위의 해당사항을 고려해서 돌렸지만 아직까지 반례가 남은듯 하네요. 7%에서 틀렸다고 나오네요. 

제가 잘못 접근 한 부분도 있다고 생각합니다.

보물찾고 싶습니다. 도와줍쇼

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