hanju0704   8년 전

분할정복을 이용하는건 알겠는데, 어떻게 구현해야될지 감이 안잡히네요.

문제를 보고

① '일단 2차원 배열을 선언 후, 내가 입력한 색종이 인풋을 저장해야겠다'

② 색종이를 4등분 분할 후, 각 종이마다 흰색이나 파란색으로 꽉차있는지 아닌지 검사하고

③ if(꽉차있을 시) --> 분할을 멈추고,

else --> ②를 반복한다.


이런 계획은 세워놓았는데, 구현한건 ①밖에 없네요.. 배열에 넣었는 놨는데 이거를

4등분하는 코드를 어떻게 작성해야할지도 모르겠네요. 사실 배열에 저장하는게 효율적인 방법일지도 의문이고요ㅠ

1시간정도 고민하다가 질문 올려봅니다. 이 문제를 어떻게 해결해나가야할까요?ㅠㅠ

baekjoon   8년 전

재귀 호출을 이용하면 편리하게 구현할 수 있습니다.

(x,y)에서 길이가 l인 정사각형을 검사하는 것을 go(int x, int y, int l)와 같은식으로 구현을 했다면

4등분하는 코드는

go(x, y, l/2)

go(x,y+l/2,l/2)

go(x+l/2,y,l/2)

go(x+l/2,y+l/2,l/2)

로 재귀호출을 해서 구현할 수 있습니다

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