[백준] 1074번 Z C++ 풀이

---

알고리즘 분류

• 분할정복
• 재귀

---

문제 설명

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

---

입력 설명

첫째 줄에 정수 N, r, c가 주어진다.

---

출력 설명

r행 c열을 몇 번째로 방문했는지 출력한다.

---

예제 입력

2 3 1

3 7 7

1 0 0

4 7 7

10 511 511

10 512 512

---

예제 출력

11

63

0

63

262143

786432

---

아이디어

그림에서 항상 4칸을 기준으로 (0, 0) -> (0, 1) -> (1, 0) -> (1, 1) 칸을 순서로 방문한다.

그리고 (0, 0)번째 칸의 숫자는 (r/2, c/2)칸 숫자 * 4를 한 값과 동일하다.

이를 재귀를 통해 구현한다.

---

알고리즘

4칸을 기준으로 R행 C열이 어느 칸에 있는지 먼저 알아낸다.

(0, 0)번째 칸의 숫자는 (r/2, c/2)칸 숫자 * 4를 한 값과 동일하므로 위에서 알아낸 값을 여기에 더한다.

이를 재귀적으로 구현하면

int loop(int n, int r, int c)
{
    if(n == 0) return 0;
    return (2*(r%2)+(c%2)) + 4 * (loop(n-1,r/2,c/2));
}

---

코드

#include <iostream>
using namespace std;
int n, r, c;
int loop(int n, int r, int c)
{
    if(n == 0) return 0;
    return (2*(r%2)+(c%2)) + 4 * (loop(n-1,r/2,c/2));
}
int main() {
    cin>>n>>r>>c;
    cout<<loop(n,r,c);
    return 0;
}

---

후기

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

이 문제도 처음에는 뭔가 풀릴 듯하면서도 안 풀려서 굉장히 오랫동안 고민했다.

이후에 찾아보니 이 방법 이외에도 푸는 방법이 다양하게 존재했다.

1. 이 방법처럼 좌푯값을 사용한 재귀

2. Z모양을 이용한 분할정복 재귀

3. 중국인의 나머지 정리를 사용

등등... 나중에 다른 방법으로도 푸는 것에 도전해 보고 싶다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!