재귀호출(재귀함수)-Z(백준1074번)

재귀함수-백준1074번 Z문제

---

---

풀이-재귀호출을 이용한 알고리즘풀이

---

package recursiveandbacktracking;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Baekjun1074ZproblemRecursive {
    static long count;
    public static long zRecursive(long powNum,int r,int c) {
        if(powNum==2) { //2x2일 경우
            //1사분면일경우
            if(r%powNum==0 && c%powNum==0) {
                return count;
            }
            //2사분면일경우 1사분면칸수를 더해준다
            else if(r%powNum==0 && c%powNum==1) {
                return count+1;
            }
            //3사분면일경우 1,2사분면칸수를 더해준다
            else if(r%powNum==1 && c%powNum==0) {
                return count+2;
            }
            //4사분면일경우 1,2,3사분면칸수를 더해준다.
            else {
                return count+3;
            }
        }else { //2x2가 아닐 경우 
            //1사분면일경우
            if((r%powNum<(powNum/2)) && (c%powNum<(powNum/2))) {
                return zRecursive(powNum/2, r, c);
            }
            //2사분면일경우 1사분면의 모든 칸수를 더해주며 재귀호출
            else if(r%powNum<(powNum/2) && (c%powNum>(powNum/2-1))) {
                count+=((powNum/2)*(powNum/2))*1;
                return zRecursive(powNum/2, r, c);
            }
            //3사분면일경우 1,2사분면의 모든 칸수를 더해주며 재귀호출
            else if((r%powNum>(powNum/2-1)) && (c%powNum<(powNum/2))) {
                count+=((powNum/2)*(powNum/2))*2;
                return zRecursive(powNum/2, r, c);
            }
            //4사분면일경우 1,2,3사분면의 모든 칸수를 더해주며 재귀호출
            else {
                count+=((powNum/2)*(powNum/2))*3;
                return zRecursive(powNum/2, r, c);
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int r=sc.nextInt();
        int c=sc.nextInt();
        long powNum=(long) Math.pow(2,N);
        System.out.println(zRecursive(powNum, r, c));
    }
}
 

이 문제를 보면 딱 떠오르는 것이있다. Z방향으로 배열을 순회하는 것이다. 그 말은 즉슨 배열을 1사분면->2사분면->3사분면->4사분면 순서로 방문을 하는 것이다. 여기서 이용되는 재귀호출의 기능은 예를들어 8x8의 배열이라면 재귀호출을 통해 4x4배열로 줄여주는 역할을 한다.(이말을 재귀호출을 통해서 큰 문제를 작은 문제로 쪼개나가는 과정이라고 생각하면 된다.) 1/4씩 배열의 크기를 줄여가며 방문한 횟수를 카운트해주는 것이다. 예를 들어 8x8의 배열의 2사분면이라면? 8x8배열에서 이미 1사분면을 지나왔으므로 (64/4)*(해당분면-1=1)의 배열만큼 방문해서 2사분면을 온것이므로 방문횟수에 (64/4)*1만큼의 수를 증가시켜주고 8x8의 2사분면인 4x4배열로 재귀를 통해 문제의 크기를 줄여준다. 그 다음의 위치가 4x4의 배열에서 몇 사분면이냐라는 것을 다시 따져서 위처럼 횟수를 증가시켜준다. 그리고 배열을 줄여가다 마지막으로 2x2의 배열이 되었을때 1사분면일때는 횟수를 0, 2사분면은 횟수를 1, .....4사분면은 횟수를 3을 증가시켜주면된다.