[Python][C++] 1074번 Z

문제

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

 

 

 

 

코드

1. Python

def recursion(n, x, y):
    global ans

    # 재귀의 종료 조건, n이 0이 될 경우 위치 (x, y)에 도달했음을 의미
    if n == 0:
        ans += x * 2 + y
        print(ans)
        return

    # 첫 번째 사분면: 좌상단 (x, y가 모두 2^n보다 작은 경우)
    if x < 2 ** n and y < 2 ** n:
        recursion(n - 1, x, y)

    # 두 번째 사분면: 우상단 (x는 작고, y는 크거나 같은 경우)
    elif x < 2 ** n and y >= 2 ** n:
        ans += 2 ** (2 * n)  # 해당 사분면 전에 탐색해야 하는 전체 항목 수 추가
        recursion(n - 1, x, y - 2 ** n)  # y 좌표 조정하여 재귀 호출

    # 세 번째 사분면: 좌하단 (x는 크거나 같고, y는 작은 경우)
    elif x >= 2 ** n and y < 2 ** n:
        ans += 2 * 2 ** (2 * n)  # 첫 번째, 두 번째 사분면 후 탐색
        recursion(n - 1, x - 2 ** n, y)  # x 좌표 조정하여 재귀 호출

    # 네 번째 사분면: 우하단 (x, y 모두 2^n보다 크거나 같은 경우)
    else:
        ans += 3 * 2 ** (2 * n)  # 세 사분면을 모두 탐색한 후 위치
        recursion(n - 1, x - 2 ** n, y - 2 ** n)  # x, y 좌표 모두 조정


N, r, c = map(int, input().split())

ans = 0
recursion(N - 1, r, c)

 

2. C++

#include <iostream>
using namespace std;

int ans = 0;  // 결과 값을 저장할 전역 변수

// 재귀 함수 정의
void recursion(int n, int x, int y) {
    // 기저 사례: 가장 작은 크기의 격자(1x1)에 도달했을 때
    if (n == 0) {
        ans += x * 2 + y;  // 위치에 따라 값을 계산하여 결과에 더함
        cout << ans;       // 최종 결과 출력
        return;
    }

    // x, y 좌표에 따라 적절한 사분면 선택
    if (x < (1 << n) && y < (1 << n)) {  // 첫 번째 사분면
        recursion(n - 1, x, y);          // 그대로 재귀 호출
    }
    else if (x < (1 << n) && y >= (1 << n)) {  // 두 번째 사분면
        ans += (1 << (2 * n));                  // 2^n * 2^n 크기 격자의 원소 수만큼 결과에 더함
        recursion(n - 1, x, y - (1 << n));      // y 좌표 조정 후 재귀 호출
    }
    else if (x >= (1 << n) && y < (1 << n)) {  // 세 번째 사분면
        ans += 2 * (1 << (2 * n));             // 두 격자 영역의 원소 수만큼 결과에 더함
        recursion(n - 1, x - (1 << n), y);     // x 좌표 조정 후 재귀 호출
    }
    else {  // 네 번째 사분면
        ans += 3 * (1 << (2 * n));             // 세 격자 영역의 원소 수만큼 결과에 더함
        recursion(n - 1, x - (1 << n), y - (1 << n));  // x, y 좌표 모두 조정 후 재귀 호출
    }
}

int main() {
    int n, r, c;

    cin >> n >> r >> c;

    recursion(n, r, c);

    return 0;
}

 

 

풀이 

차원 배열을 Z 모양으로 탐색하는 알고리즘에 대한 문제다.

Z모양대로 1부터 직접 순서를 세려고 하면 크기가 2^15 * 2^15 이기 때문에 당연히 시간초과나 메모리초과가 난다.

 

 

1. 분할 정복:
   • 전체 크기를 점차 작은 사분면으로 나눈다.
2. 재귀:
   • 각 단계에서 4개의 사분면으로 나누고, 해당 사분면이 r과 c를 포함하면 그 사분면 안에서 다시 탐색을 진행한다.
   • 위치한 사분면의 순서에 따라 방문 순서의 시작값을 계산한다.
3. 출력:
   • 최종적으로 (r, c) 위치에 도달했을 때의 순서를 출력

 

분할 정복 참고

https://ehdbs0903.tistory.com/entry/Algorithm-분할-정복Divide-and-Conquer-알고리즘

[Algorithm] 분할 정복(Divide and Conquer) 알고리즘