[백준 - 1074] Z - Python

분류: 재귀, 좌표계 /

 

문제

문제 링크

문제 설명

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

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

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

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

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

입력

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

출력

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

 

풀이

- Python

import sys 
readline = sys.stdin.readline

def search(exp, n, row, col):
    if exp == 0: return n

    w = 2**(exp-1)
    size = w**2
    
    if row >= w:
        n += 2*size
        row -= w
    if col >= w:
        n+= size
        col -= w
    return search(exp-1, n, row, col)

N, r, c = map(int, readline().split())
print(search(N, 0, r, c))

• `search(exp, n, row, col)`: 재귀적으로 범위를 좁혀가며 답을 찾아감
  • `exp`: 현재 차수(재귀 깊이, 0이면 탐색 종료)
  • `n`: `exp`차 메트릭스 좌상단 원소의 값(원점 값)
  • `row`, `col`: `exp`차 메트릭스에 대한 구하고자 하는 값의 상대좌표
  • `w`: 바로 아래 차수 메트릭스의 변의 길이
  • `size`: 바로 아래 차수 메트릭스의 원소의 개수
  • `if 문`: `row`, `col`, `n`을 바로 아래 차수 메트릭스에 대한 값으로 업데이트
  • 재귀문: 차수를 내려 재귀 호출

- C++

#include <iostream>
using namespace std;

int z(int n, int start, int r, int c) {
    if(n == 0) return start;
    int half = 1 << --n;
    if(r >= half) {
        r -= half;
        start += 2*half*half;
    }
    if(c >= half) {
        c -= half;
        start += half*half;
    }
    return z(n, start, r, c);
}

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

    int N, r, c; cin >> N >> r >> c;
    cout << z(N, 0, r, c);
}

 

- 오답

import sys 
readline = sys.stdin.readline

def fill(n, start, start_row, start_col):
    matrix[start_col][start_row] = start
    if n == 1:
        matrix[start_col][start_row] = start + 1
        matrix[start_col+1][start_row] = start + 2
        matrix[start_col+1][start_row+1] = start + 3
        return
    
    width = 2**(n-1)
    size = width**2
    fill(n-1, start, start_row, start_col)
    fill(n-1, start+size, start_row+width, start_col)
    fill(n-1, start+2*size, start_row, start_col+width)
    fill(n-1, start+3*size, start_row+width, start_col+width)

N, r, c = map(int, readline().split())
matrix = [[0]*2**N for _ in range(2**N)]
fill(N, 0, 0, 0)
print(matrix[c][r])

메모리 초과, N이 최대 15인 조건을 확인하지 못함

 

오답 풀이를 재귀 식으로 옮겨보면 다음과 같이 만들 수 있다.

#include <iostream>
using namespace std;

int z(int n, int r, int c) {
    if(n == 0) return 0;
    int half = 1<<(n-1);
    if(r < half && c < half) return z(n-1, r, c);
    if(r < half && c >= half) return half*half + z(n-1, r, c-half);
    if(r >= half && c < half) return 2*half*half + z(n-1, r-half, c);
    return 3*half*half + z(n-1, r-half, c-half);
}

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

    int N, r, c; cin >> N >> r >> c;
    cout << z(N, r, c);
}