C - [백준1074] Z (feat. 재귀적 사고, 분할정복)

참고 포스트

 

2024.12.27 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

[알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

2024.12.28 - [Computer Science/알고리즘 문제] - C - [Backjoon 2630] 색종이 만들기 (feat. 재귀적 사고, 분할정복)

 

 

 

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2 

3 7 7

예제 출력 2 

63

예제 입력 3

1 0 0

 

예제 출력 3 

0

예제 입력 4 복사

4 7 7

예제 출력 4

63

예제 입력 5 

10 511 511

예제 출력 5 

262143

예제 입력 6

10 512 512

 

예제 출력 6 

786432

 

 

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

BOJ 1074: Z 탐색 문제 풀이

문제 개요

Z 모양의 탐색 패턴을 따르는 2^N×2^N 크기의 2차원 배열에서, 주어진 좌표 (r,c)가 몇 번째로 방문되는지 찾아야 하는 문제입니다.

---

Chekpoint

바로 직전 포스트였던 색종이 만들기 (https://rnasterofmysea.tistory.com/63) 문제에서 재귀적 사고에 대해 감을 잡았다면 직관적인 사진이 주어졌기 때문에, 기저 조건(base case)과 재귀 조건(recruison base)를 쉽게 정의할 수 있는 문제이다.

 

 

기저 조건보다 재귀 조건 즉, 규칙을 정의하면 기저 조건은 자연스럽게 따라오는 문제이다.

상단의 그림을 보면 알 수 있듯이 4등분 단위로 Z를 그리고 있다. 찾고자 하는 목표값이 어느 등분에 해당되는지 판단하고 그 등분안에서도 어떤 등분에 해당하는지 쭉쭉 내려가면 된다. (재귀조건)

 

Z가 그려지려면 배열의 최소 크기가  2*2이다. 2*2 배열에서 한단계 더 내려가면 1*1 배열, 즉 값이 하나만 있는 배열 까지 내려가게 되는데 그게 바로 목표값이되며 재귀의 종료 조건이다.

다시 말해서 배열의 크기가 1일 때가 기저조건이 된다는 뜻이다.

문제 풀이

1. Z 탐색 패턴

배열의 크기가 2×2라고 가정했을 때, 탐색 순서는 다음과 같습니다:

0  1
2  3

배열이 더 커질수록, 탐색은 다음과 같은 Z 모양 패턴으로 진행됩니다:

• 크기 4×4 (Z 모양 순서):

 0   1   4   5
 2   3   6   7
 8   9  12  13
10  11  14  15

• 크기 8×8: 크기가 커질수록 Z 패턴은 좌상 → 우상 → 좌하 → 우하 순서로 반복됩니다.

2. 사분면 나누기

배열을 4개의 사분면으로 나누어 생각할 수 있습니다.

• 1번 사분면: 왼쪽 위 (r<중간r < 중간, c<중간c < 중간)
• 2번 사분면: 오른쪽 위 (r<중간r < 중간, c≥중간c \geq 중간)
• 3번 사분면: 왼쪽 아래 (r≥중간r \geq 중간, c<중간c < 중간)
• 4번 사분면: 오른쪽 아래 (r≥중간r \geq 중간, c≥중간c \geq 중간)

3. 탐색 순서의 계산

각 사분면의 방문 시작 번호는 다음과 같이 계산됩니다:

• 1번 사분면: 시작 번호는 0.
• 2번 사분면: 시작 번호는 1×사분면의크기.
• 3번 사분면: 시작 번호는 2×사분면의크기.
• 4번 사분면: 시작 번호는 3×사분면의크기.

사분면의 크기

 

4. 재귀적 접근

N=2라면, 4×4배열에서 Z 패턴을 따르며, 크기를 절반씩 줄여 탐색 좌표를 재귀적으로 찾아갑니다:

1. 현재 좌표가 속한 사분면을 확인합니다.
2. 해당 사분면의 시작 번호를 더한 뒤, 작아진 배열에서 새로운 좌표로 재귀 호출합니다.
3. 배열의 크기가 1 * 1이 되면 종료하고, 탐색 순서를 반환합니다.

---

코드 구현

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

#include <stdio.h>

int count = 0;

void recursion(int x, int y, int size, int r, int c) {
    // Base case: 배열 크기가 1일 때
    if (size == 1) {
        if (x == c && y == r) {
            return;
        }
    }

    // 배열 크기를 절반으로 나눔
    int new_size = size / 2;

    // 반복문으로 사분면 탐색
    for (int i = 0; i < 2; i++) {      // 행 방향(상하)
        for (int j = 0; j < 2; j++) {  // 열 방향(좌우)
            int nx = x + j * new_size; // 새로운 x 좌표
            int ny = y + i * new_size; // 새로운 y 좌표

            // 현재 사분면에 r, c가 속하는지 확인
            if (ny <= r && r < ny + new_size && nx <= c && c < nx + new_size) {
                count += (i * 2 + j) * new_size * new_size; // 사분면 카운트 추가
                recursion(nx, ny, new_size, r, c);         // 해당 사분면으로 재귀 호출
                return; // 탐색 완료 후 반환
            }
        }
    }
}

int main() {
    int N, r, c;
    scanf("%d %d %d", &N, &r, &c);

    int size = 1 << N; // 배열 크기: 2^N
    recursion(0, 0, size, r, c);

    printf("%d", count);
    return 0;
}

 

 

아래는 코드에 대한 상세한 해설입니다.

---

코드 설명

코드 구조

1. 전역 변수
   • 탐색 과정에서 현재까지 방문한 순서를 저장하는 변수입니다.

int count = 0;

1. recursion 함수
   • (x,y)(x, y): 현재 사분면의 시작 좌표.
   • size: 현재 사분면의 크기.
   • (r,c)(r, c): 목표 좌표.

void recursion(int x, int y, int size, int r, int c)

기본 동작

1. 기저 조건
   • 사분면의 크기가 1×11 \times 1일 때, 현재 좌표가 (r,c)(r, c)와 같다면 탐색을 종료합니다.

if (size == 1) {
    if (x == c && y == r) {
        return;
    }
}

1. 사분면 분할
   • 배열을 4개의 사분면으로 나눕니다. 새로운 사분면의 크기는 기존 크기의 절반입니다.

int new_size = size / 2;

1. 사분면 탐색

for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
        int nx = x + j * new_size;
        int ny = y + i * new_size;

        if (ny <= r && r < ny + new_size && nx <= c && c < nx + new_size) {
            count += (i * 2 + j) * new_size * new_size;
            recursion(nx, ny, new_size, r, c);
            return;
        }
    }
}

 

• 반복문을 사용하여 4개의 사분면을 탐색합니다.
  • i: 행 방향(상하).
  • j: 열 방향(좌우).
• 각 사분면의 시작 좌표 (nx,ny)를 계산합니다.
• 현재 좌표 (r, c)가 해당 사분면에 속하는지 확인한 뒤:
  • 사분면 순서 추가: (i×2+j) × new_size^2 (사분면 크기만큼 순서를 증가).
  • 해당 사분면으로 재귀 호출.

1. 재귀 호출 종료
   • r,cr, c가 속한 사분면을 찾고 탐색을 마치면 return으로 종료합니다.
2. main 함수
   • 입력받은 N,r,cN, r, c를 기반으로 배열의 크기를 2N2^N로 설정합니다.
   • (0,0)(0, 0)에서 탐색을 시작합니다.
   • 탐색 결과 count를 출력합니다.

 

---

동작 과정

입력 예제

N = 2, r = 3, c = 1

배열 분할 과정

1. 처음 배열: 4×4
   • 크기: 4×4, 시작 좌표: (0,0).
   • 좌표 (3,1)은 3번 사분면에 속함.
   • count += 8 (3번 사분면의 시작 번호).
   • 새로운 탐색 크기: 2×2.
2. 두 번째 배열: 2×2
   • 크기: 2×2, 시작 좌표: (2,0)(2, 0).
   • 좌표 (3,1)(3, 1)은 4번 사분면에 속함.
   • count += 3 (4번 사분면의 시작 번호).
   • 새로운 탐색 크기: 1×1
3. 마지막 배열: 1×1
   • 크기: 1×1, 시작 좌표: (3,1)(3, 1).
   • 기저 조건에 도달, 탐색 종료.

출력

count = 11

---

시간 복잡도

• 배열의 크기를 절반으로 줄이며 탐색하므로, 재귀 호출 횟수는 O(log⁡N)입니다.
• 각 호출당 상수 시간 연산을 수행하므로, 최종 시간 복잡도는 O(log⁡N)입니다.

---

결론

이 코드는 문제를 재귀적으로 해결하며, 배열을 Z 패턴으로 탐색하는 과정을 정확히 구현했습니다. 사분면 분할과 탐색 순서 계산을 통해 O(log⁡N)의 효율적인 탐색이 가능하며, 문제의 핵심인 분할 정복(Divide and Conquer) 접근 방식을 잘 보여줍니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.