[백준 1074] Z (C#, C++) - soo:bak

문제 링크

1074번 - Z

설명

크기가 2^N × 2^N인 정사각형 배열을 Z 모양으로 순회할 때,

특정 좌표가 몇 번째로 방문되는지를 구하는 문제입니다.

Z 모양 순회란, 배열을 네 부분으로 나누어

• 왼쪽 위 → 오른쪽 위 → 왼쪽 아래 → 오른쪽 아래

순서로 방문하는 것을 말합니다.

입력으로는 크기 지수 N과 확인하고자 하는 위치 (r, c)가 주어지며,

Z 순회에서 해당 좌표가 몇 번째로 방문되는지를 출력하는 것이 목적입니다.

접근법

전체 배열은 2^N × 2^N 크기의 정사각형입니다.

이 때, Z 순회의 순서대로 탐색을 진행하기 위해,

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 의 네 영역으로 나누어

각 영역을 왼쪽 위부터 차례대로 재귀적으로 탐색합니다.

이때 각 영역을 탐색하기 전에, 해당 좌표가 그 영역에 포함되어 있는지를 먼저 확인합니다.

만약 포함되어 있지 않다면:

• 그 영역은 재귀 호출 없이 건너뛰고
• 그 영역에 해당하는 칸 수만큼 순서를 미리 더해줍니다.

반대로 좌표가 포함된 영역을 만나면:

• 그 영역을 다시 네 부분으로 나누고 같은 방식으로 재귀 탐색을 이어갑니다.

이 과정을 배열의 크기가 1 × 1이 될 때까지 반복하면,

마지막에 누적된 값이 해당 좌표의 방문 순서가 됩니다.

---

Code

C#

using System;

class Program {
  static int ans = 0;
  static int targetR, targetC;

  static void Solve(int r, int c, int size) {
    if (r == targetR && c == targetC) {
      Console.WriteLine(ans);
      return;
    }

    if (targetR >= r && targetR < r + size &&
        targetC >= c && targetC < c + size) {
      int half = size / 2;
      Solve(r, c, half);
      Solve(r, c + half, half);
      Solve(r + half, c, half);
      Solve(r + half, c + half, half);
    } else {
      ans += size * size;
    }
  }

  static void Main() {
    var tokens = Console.ReadLine().Split();
    int n = int.Parse(tokens[0]);
    targetR = int.Parse(tokens[1]);
    targetC = int.Parse(tokens[2]);

    Solve(0, 0, 1 << n);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n, idxRow, idxCol;
int ans = 0;

void solve(int row, int col, int size) {
  if (row == idxRow && col == idxCol) {
    cout << ans << "\n";
    return;
  }

  if (idxRow >= row && idxRow < row + size &&
      idxCol >= col && idxCol < col + size) {
    int halfSize = size / 2;
    solve(row, col, halfSize);
    solve(row, col + halfSize, halfSize);
    solve(row + halfSize, col, halfSize);
    solve(row + halfSize, col + halfSize, halfSize);
  } else ans += size * size;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> idxRow >> idxCol;
  solve(0, 0, 1 << n);

  return 0;
}