[재귀함수] BAEKJOON '1074'번 'Z'문제 (C++/python)

문제 : www.acmicpc.net/problem/1074

1074번: Z

 

 

 

• 문제 해결 아이디어

    1.  사각형을 기저모양까지 잘라가며(재귀적으로) 해결한다.

   

    2.  n을 입력받으면, 한 변의 길이가 2^n인 사각형이 만들어진다.

    3.  Z모양으로 탐색을 하기 위해선, 기저모양 (2 x 2 사각형)이 될 때 까지 재귀함수 호출할 때,

        사각형의 시작값과 길이를 넘겨주어야 된다.

 

        처음 시작 부분을 (a,b)라 하고 사각형이 2 x 2 모양이 아니라고 하면, 위 그림의 파란 색 부분마다 함수를 다시 실행해주어야 된다.

        이때, 순서는 Z모양을 유지하도록 함수를 호출한다 (1,2,3,4번 순서대로).

 

 

    4.  탐색 횟수를 세는 전역변수를 선언하여준다.

 

    5.  탐색 중 입력받았던 좌표값을 찾는 즉시 현재까지 탐색한 횟수를 출력하고 프로그램을 마친다.

 

 

 

• python

def visit(n, r, c):
    global cnt
    if n==2:
        if r == R and c == C:
            print(cnt)
            return
        cnt += 1

        if r == R and c+1 == C:
            print(cnt)
            return
        cnt += 1

        if r+1 == R and c == C:
            print(cnt)
            return
        cnt += 1

        if r+1 == R and c+1 == C:
            print(cnt)
            return
        cnt += 1
    else:
        visit(n/2, r, c)
        visit(n/2, r, c + n/2)
        visit(n/2, r + n/2, c)
        visit(n/2, r + n/2, c + n/2)


cnt = 0
n, R, C = map(int,input().split(' '))
visit(2**n, 0, 0)

 

 

 

• c++

#include "iostream"
#include "cmath"

using namespace std;

int R, C, cnt= 0;

void visit(int n, int r, int c){
    
    if(n == 2){                  // 기저모양 (2*2 사각형)
        if(r == R && c == C){    // 찾고자 하는 값이 현재 칸인 경우
            printf("%d\n",cnt);
            return;
        }
        cnt++;                   // 한번 확인할 때 마다, 횟수를 1씩 증가시킨다.
        if(r == R && c+1 == C){  // 찾고자 하는 값이 현재의 오른쪽 칸일 경우
            printf("%d\n",cnt);
            return;
        }
        cnt++;
        
        if(r+1 == R && c == C){  // 찾고자 하는 값이 현재의 아래쪽 칸일 경우
            printf("%d\n",cnt);
            return;
        }
        cnt++;
        
        if(r+1 == R && c+1 == C){ // 찾고자 하는 값이 현재의 오른쪽 아래칸일 경우
            printf("%d\n",cnt);
            return;
        }
        cnt++;
    }
    
    else{                         // 기저모양이 아닐 시 호출 순서는 Z모양으로 호출한다.
        visit(n/2, r, c);
        visit(n/2, r, c + n/2);
        visit(n/2, r + n/2, c);
        visit(n/2, r + n/2, c + n/2);
        
    }
}


int main(){
    
    int N;
    scanf("%d%d%d",&N,&R,&C);
    
    visit(pow(2,N) ,0, 0);
    
    return 0;
}