[백준 1074번] Z (java)

 

1074번: Z

 

분할하여 같은 동작을 반복하기 때문에 재귀를 이용하여 풀 수 있다.

처음에는 1, 2, 3, 4 분면의 모든 경우의 수를 다 재귀함수 호출을 했더니 시간 초과가 나왔다.

그래서 조건문을 이용하여 (r, c)이 포함된 사각형만 선별적으로 재귀를 실행하도록 변경하였다.

 

2차원 배열의 정보를 가장 왼쪽 위 좌표(i, j) 와 한 변의 길이 size로 나타낼 때,

이 2차원 배열을 4등분한 각각의 사각형은 다음과 같이 표현이 가능하다.

 

    - 2사분면  : (i, j) , size/2

    - 1사분면 : (i, j + size/2), size/2

    - 3사분면 : (i + size/2, j), size/2

    - 4사분면 : (i + size/2, j + size/2), size/2 

 

만약 (r, c)가 2사분면에 포함된다면 가장 처음 방문하는 위치는 0번째로 방문하게 된다.

(r, c)가 1사분면에 포함된다면 가장 처음 방문하는 위치는 (size/2)*(size/2) 번째로 방문하게 된다.

만약 size가 8일 경우, (size/2)*(size/2) = 4*4 = 16이 된다.

즉, 1사분면 구역에서 제일 처음 방문하는 경우는 0번째가 아니라 16번째가 되야 한다.

(r, c)가 3사분면에 포함된다면 가장 처음 방문하는 위치는 (size/2)*(size/2)*2 번째로 방문하게 된다.

size가 8일 경우, (size/2)*(size/2) = 4*4*2 = 32이 된다.

즉, 3사분면 구역에서 제일 처음 방문하는 경우는 32번째가 되야 한다.

(r, c)가 4사분면에 포함된다면 가장 처음 방문하는 위치는 (size/2)*(size/2)*3 번째로 방문하게 된다.

size가 8일 경우, (size/2)*(size/2) = 4*4*3 = 48이 된다.

즉, 4사분면 구역에서 제일 처음 방문하는 경우는 48번째가 되야 한다.

 

이런식으로 계속 재귀를 통해 4분할을 진행하면서 반복한다.

첫 방문한 경우가 몇번째에 해당하는지 확인한 후, 그 값을 더해준다.

예를 들어, (1,5) 위치의 경우 그 사분면 내에서는 3번째로 방문하지만 해당 사분면에서의 첫 방문이 16번째에 해당하므로 3에다 16을 더해줘야 한다. 3 + 16 = 19번째

 

size = 1 일 때까지, 즉 더 이상 분할할 수 없을 때까지 재귀를 반복한다. -> base case

 

 

소스코드 :