[BOJ] 백준 1074번: Z

문제

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

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

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

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

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

 

풀이

저는 이 문제를 처음에 배열에 담아서 모든 위치를 기록하고 풀면 어떨까? 라는 생각을 해봤습니다만 최대 범위인 N=15가 되었을 때 배열의 사이즈는 32768*32768의 범위이기에 시간제한인 0.5초만에 해결하기란 불가능하다고 생각했습니다.

따라서 재귀로 배열 한 변의 길이가 2가 될 때까지 4칸으로 분할하고 위치별로 쪼개는 방식을 채택하여 분할 정복을 하였습니다. 마지막으로 길이가 2가 되었을 때는 위치별로 값을 더해주었습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder("");

    static int N, r, c, ans = 0;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
    }

    static void process(int length, int r, int c){
        if(length == 2){
            if(r == 0 && c == 1) ans += 1;
            else if(r == 1 && c == 0) ans += 2;
            else if(r == 1 && c == 1) ans += 3;
            System.out.println(ans);
            return;
        }

        int cnt = 0, comR=0, comC=0;
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                if(comR <= r && r < comR+length/2 && comC <= c && c < comC + length/2){
                    ans += cnt*(length/2)*(length/2);
                    r -= comR; c -= comC;
                    process(length / 2, r, c);
                    break;
                }
                comC += length/2;
                cnt += 1;
            }
            comR += length/2;
            comC = 0;
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        process((int)Math.pow(2,N), r, c);
    }
}

 

 

<출처>

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