백준 1074번 [Z](C++)-yes6686- 티스토리

백준 문제 풀이: 1074 [Z]

---

문제 링크: https://www.acmicpc.net/problem/1074

문제 설명:

2^n x 2^n 크기의 2차원 배열을 Z 모양으로 탐색하며, 배열의 특정 위치 (r, c)에 몇 번째로 도달하는지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <cmath>
using namespace std;

int n, r, c;
int cnt = 0;

void Z(int x, int y, int s) {
    if (x == r && y == c) {
        cout << cnt << '\n';
        return;
    } else if (r >= x && c >= y && r < x + s && c < y + s) {
        Z(x, y, s / 2);
        Z(x, y + s / 2, s / 2);
        Z(x + s / 2, y, s / 2);
        Z(x + s / 2, y + s / 2, s / 2);
    } else {
        cnt += s * s;
    }
}

int main() {
    cin >> n >> r >> c;
    Z(0, 0, pow(2, n));
}

---

코드 설명

• 재귀적 분할: 2차원 배열을 4개의 사분면으로 나누어 재귀적으로 탐색합니다.
• 탐색 조건:
  • 현재 사분면이 목표 위치 (r, c)를 포함하고 있으면 해당 사분면을 다시 분할하여 탐색합니다.
  • 포함하지 않는 경우, 현재 사분면에 포함된 모든 칸의 수를 카운트에 더하고 종료합니다.
• 종료 조건: 목표 위치에 도달하면 현재 카운트를 출력하고 재귀를 종료합니다.
• 시간 복잡도: O(4^log(n)) ≈ O(n^2), 재귀적으로 배열을 분할하며 각 단계에서 4개의 부분에 대해 연산 수행.

---

결과

입력된 배열 크기와 위치에 따라 Z 탐색 순서를 계산하며, 목표 위치 (r, c)에 도달했을 때의 순서를 출력합니다.

더 나은 알고리즘이나 질문이 있다면 댓글로 남겨주세요!