백준 1074번 : Z

1. 문제

문제

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[][] arr;
    static int count = 0;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int m = (int) Math.pow(2, N);
        arr = new int[m][m];
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        dp(0, 0, m - 1, m - 1);
        System.out.println(arr[r][c]);
    }

    static void dp(int startRow, int startCol, int endRow, int endCol) {
        int rowLen = endRow - startRow;
        int colLen = endCol - startCol;
        if (rowLen == 1 && colLen == 1) {
            arr[startRow][startCol] = count++;
            arr[startRow][endCol] = count++;
            arr[endRow][startCol] = count++;
            arr[endRow][endCol] = count++;
        } else {
            dp(startRow, startCol, startRow + rowLen / 2, startCol + colLen / 2);
            dp(startRow, startCol + colLen / 2 + 1, startRow + rowLen / 2, endCol);
            dp(startRow + rowLen / 2 + 1, startCol, endRow, startCol + colLen / 2);
            dp(startRow + rowLen / 2 + 1, startCol + colLen / 2 + 1, endRow, endCol);
        }
    }

}

3. 해설

• 동적 계획법으로 모든 배열의 값을 정하는 방식
• 문제점 : 해당하는 좌표의 값만 필요한데 불필요하게 모든 값을 초기화 하느라 배열 메모리를 너무 많이 잡아먹는다
  → 위치에 따라 시작 값을 받아와서 배열 없이 값을 구하도록 한다.

4. 다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int count = 0;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int m = (int) Math.pow(2, N);
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        System.out.println(find(0,0, m, r, c));;
    }

    static int find(int startRow, int startCol, int size, int targetRow, int targetCol) {
        if (size == 1) {
            return count;
        }
        int newSize = size / 2;
        int areaCount = newSize * newSize;

        // 1번 사분면
        if (targetRow < startRow + newSize && targetCol < startCol + newSize) {
            return find(startRow, startCol, newSize, targetRow, targetCol);
        }
        // 2번 사분면
        else if (targetRow < startRow + newSize && targetCol >= startCol + newSize) {
            count += areaCount;
            return find(startRow, startCol + newSize, newSize, targetRow, targetCol);
        }
        // 3번 사분면
        else if (targetRow >= startRow + newSize && targetCol < startCol + newSize) {
            count += 2 * areaCount;
            return find(startRow + newSize, startCol,newSize, targetRow, targetCol);
        }
        // 4번 사분면
        else {
            count += 3 * areaCount;
            return find(startRow + newSize, startCol + newSize, newSize, targetRow, targetCol);
        }
    }

}

• 타겟 좌표가 현재 사이즈 기준으로 어느 위치에 속하는지 확인 한후 사분면에 따라 count에 적절한 값을 더한 후 찾는다.