[BOJ] 백준 1074. Z

▶문제설명

[BOJ] 백준 1074. Z

https://www.acmicpc.net/problem/1074

▶ 설계

---

문제에서 주어진 그림을 관찰해보자.

N이 2인 경우 순회하는 순서를 나타내는 그림이다.

변의 길이가 2^2 = 4이다.

4등분하여 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단을 순서대로 방문해야한다.

즉, 변의 길이가 2^N인 사각형을 더이상 등분하지 못할 때까지 4등분할 수 있는지를 묻는 문제이다.

변의 길이가 2^N인 사각형을 

가능한 한 4등분해서 Z가 시작되는 위치의 좌표와 변의 길이를 2로 나눈 값을 인자로 넣어서 재귀호출 하면 될 것으로 보인다.

규칙을 파악했다면 N이 3인 경우에는 어떻게 되는지 그려보자.

편의상 같은 숫자가 적힌 것으로 붙여넣었지만, 오른쪽 상단은 16~31, 왼쪽 하단은 32 ~47, 오른쪽 하단은 48~63의 숫자가 들어가야 한다.

변의 길이는 2^3 = 8이다.

변의 길이를 반으로 줄여서 4등분하여 함수를 재귀호출하면 될 것으로 보인다.

▶ 구현

---

getAnswer라는 이름의 함수를 재귀적으로 구현해서 문제를 해결해보자.

int main(){
    scanf("%d %d %d",&N,&R,&C);
    getAnswer(0,0,(1<<N));
    printf("%d",answer);
}

이렇게 메인문에 한번의 함수 호출로 정답을 구하고 출력하도록 구현했다.

0,0에서 시작하고 한 변의 길이로 2^N 값을 인자로 넣어주었다.

2^N은 1<<N으로 나타낼 수 있다.

bool getAnswer(int r, int c, int size){
    if(size == 1){
        cnt += 1;
        return false;
    }
 
    if(!(r<=R && R<r+size && c<=C && C<c+size)){
        cnt += size*size;
        return false;
    }
    
    return false;
}

getAnswer()는 사각형의 왼쪽 상단 꼭지점의 좌표와 한 변의 길이를 매개변수로 받는다.

종료 조건으로는 한 변의 길이가 1이 됐을 때 전역변수 cnt를 1 증가시키고 false를 반환한다.

그리고 입력으로 주어진 좌표가 해당 사각형 내부에 존재하지 않을 경우 cnt를 size*size만큼 증가시키고 false를 반환하여 불필요한 연산을 줄였다.

우리는 입력으로 주어진 행 R과 열 C가 몇 번째로 방문되는지 구해야 한다.

bool getAnswer(int r, int c, int size){
    if(size == 1){
        if(R == r && C == c){
            answer = cnt;
            return true;
        }
        cnt += 1;
        return false;
    }
 
    if(!(r<=R && R<r+size && c<=C && C<c+size)){
        cnt += size*size;
        return false;
    }
    
    return false;
}

위와 같이 (R, C)를 방문했을 때만 answer 값을 저장하고 true를 반환하도록 구현했다.

그러면 getAnswer()가 true를 반환했을 때 더이상 재귀 호출되지 않도록 구현할 수 있게 된다.

불필요한 함수 호출을 줄이기 위함이다.

이제 재귀 호출이 일어나는 부분을 구현해보자.

bool getAnswer(int r, int c, int size){
    if(size == 1){
        if(R == r && C == c){
            answer = cnt;
            return true;
        }
        cnt += 1;
        return false;
    }
 
    if(!(r<=R && R<r+size && c<=C && C<c+size)){
        cnt += size*size;
        return false;
    }
    
    int m = size/2;
    for(int i=0; i<2 ;i++){
        for(int j=0; j<2 ;j++){
            if(getAnswer(r+i*m, c+j*m, m))
                return true;
        }
    }
    return false;
}

size를 2로 나눈 값인 m을 이용해서 사각형을 4등분하여 재귀호출한다.

line 17~22에서 등분된 사각형의 왼쪽 상단 꼭지점의 좌표 ( r+i*m, c+j*m )과 m을 인자로 넣어 함수를 재귀호출한다.

i와 j는 0, 1이 될 수 있는데, m을 곱해서 r과 c에 더해주면 4등분된 사각형의 왼쪽 상단 꼭지점의 좌표가 된다.

getAnswer(r, c, m);

getAnswer(r, c+m, m);

getAnswer(r+m, c, m);

getAnswer(r+m, c+m, m);

2중 포문이 아니라 위와 같이 일일이 4번 호출해주는 것과 동일하다.

▶ 결과

---

▶Solution

---

[소스코드 보기]