[백준] Z

🔗 문제 보기 - [백준] Z

📖 문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    static int N, r, c, count = 0;  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());       //  
        r = Integer.parseInt(st.nextToken());  
        c = Integer.parseInt(st.nextToken());  
  
        int pow = (int)Math.pow(2, N);  
  
        findIndex(0, 0, pow);  
        System.out.println(count);  
    }  
  
    private static void findIndex(int row, int col, int size) {  
        if(size == 1) {  
            return;  
        }  
        int halfSize = size / 2;  
        int blockSize = halfSize * halfSize;  
  
        if(r < row + halfSize && c < col + halfSize) {          // 좌상  
            findIndex(row, col, halfSize);  
        } else if(r < row + halfSize && c >= col + halfSize) {   // 우상  
            count += blockSize;  
            findIndex(row, col + halfSize, halfSize);  
        } else if(r >= row + halfSize && c < col + halfSize) {   // 좌하  
            count += blockSize * 2;  
            findIndex(row + halfSize, col, halfSize);  
        } else {   // 우하  
            count += blockSize * 3;  
            findIndex(row + halfSize, col + halfSize, halfSize);  
        }    }  
}

🧩 코드풀이

처음 문제를 해결할 때 배열로 처리하려고 했는데, 그런식으로 처리하게 되면 배열의 크기가 너무 커져서 메모리 초과가 발생했습니다.
이후에는 분할정복으로 문제를 해결했습니다.
1. findIndex 메소드를 호출할 때 마다 해당하는 사분면에 따라 count 값을 더해주는 식으로 문제를 풉니다.
2. 1사분면이면 다시 findIndex를 호출, 이후 사분면들은 이전 사분면의 크기 이상의 index 값을 갖기 때문에 count에 blockSize * N -1 값을 더해줍니다.
3. 마지막 size가 1일 때 구해지는 count의 값이 정답이 됩니다.