2589번 - 보물섬
음.. 죄송합니다 코드가 조금 복잡하게 됬습니다.
제가 구현해보려고 한 부분을 조금 설명드리겠습니다.
일반적인 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%에서 틀렸다고 나오네요.
제가 잘못 접근 한 부분도 있다고 생각합니다.
보물찾고 싶습니다. 도와줍쇼
댓글을 작성하려면 로그인해야 합니다.
cirly 6년 전
음.. 죄송합니다 코드가 조금 복잡하게 됬습니다.
제가 구현해보려고 한 부분을 조금 설명드리겠습니다.
일반적인 bfs로 구현 할 수 도 있지만, 조금 더 생각해서 시작점인 부분을 반도로 설정해 chkpenninsula 함수를 이용해 삼면이 바다일경우 bfs를 돌리고 그부분만 찾아서 bfs를 덜돌려 조금 효율적이지 않을까 생각해서 구현했지만 생각보다 반례가 많더라고요.
예시:
그래서 고려해서 다시한번 cntIsland로 섬의 개수를 설정후 다시 한번 bfs를 위의 해당사항을 고려해서 돌렸지만 아직까지 반례가 남은듯 하네요. 7%에서 틀렸다고 나오네요.
제가 잘못 접근 한 부분도 있다고 생각합니다.
보물찾고 싶습니다. 도와줍쇼