[Java] BAEKJOON 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

---

예제 입력 1

2 3 1

예제 출력 1

11

---

예제 입력 2

3 7 7

예제 출력 2

63

---

예제 입력 3

1 0 0

예제 출력 3

0

---

예제 입력 4

4 7 7

예제 출력 4

63

---

예제 입력 5

10 511 511

예제 출력 5

262143

---

예제 입력 6

10 512 512

예제 출력 6

786432

---

Java code

import java.util.Scanner;

public class Main {
    static long ff(int N, int r, int c) {
        int M = (int) Math.pow(2, N);
        long value = M * M / 4;

        if (N == 1) {
            if (r == 0 && c == 0) return 0;//2사분면
            else if (r == 0 && c == 1) return 1;//1사분면
            else if (r == 1 && c == 0) return 2;//3사분면
            else if (r == 1 && c == 1) return 3;//4사분면
        }
        M /= 2;
        if (r < M && c < M) return ff(N - 1, r, c);//2사분면
        else if (r < M && c >= M) return value + ff(N - 1, r, c % M);//1사분면
        else if (r >= M && c < M) return value * 2 + ff(N - 1, r % M, c);//3사분면
        else if (r >= M && c >= M) return value * 3 + ff(N - 1, r % M, c % M);//4사분면
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int r = sc.nextInt();
        int c = sc.nextInt();
        System.out.println(ff(N, r, c));
    }
}

---

풀이

 

먼저 이 문제는 그림을 그려서 풀어야 합니다

 

우선 예시로 8*8의 2차원 배열에 (7,7) 의 값을 구하는 방법으로 설명하면서 알려드리겠습니다

 

이 2차원 배열에 각각 제 1 사분면 ~ 제 4사분면까지의 구역을 나눕니다 그러면

사분면

 

 

 

제 1사분면은 1

 

제 2사분면은 0

 

제 3사분면은 2

 

제 4사분면은 3

8 x 8

이런식으로 큰 구역을 정해줍니다

 

(7 , 7)이 해당 하는 곳은 4 사분면으로 3이라는 값이 있는 곳입니다

 

하지만 3만 출력하면 값이 맞지 않습니다

 

저는 이 수치를 어떤식으로 해결했냐면 재귀함수 답게 value + ff라는 재귀함수를 호출 했습니다 그러면

 

8 * 8 크기의 (7 ,7)의 값을 찾을 때

 

한변의 길이가 8이니까 8의 절반인 4라는 값을 기준으로

 

1사분면 : (행 < 4 && 열 >= 4 )

 

2사분면 : (행 < 4 && 열 < 4 )

 

3사분면 : (행 >= 4 && 열 < 4 )

 

4사분면 : (행 >= 4 && 열 >= 4 )

 

이런식으로 기준을 만들어 줍니다

제 코드에서 if ~ else if 문의 조건 부분이 저렇게 해당합니다

 

(7, 7)은 4사분면에 해당하므로 value * 3값을 더한 상태로 다시 ff재귀함수를 불러옵니다

 

 

여기서 value는 나눠진 구역에 해당하는 첫 번째 값이므로

value값은 8 * 8 / 4     =>   최대값 / 4 = 16이 되도록 만들었습니다.

 

밑에 표를 보시면

 

1사분면은  + 16          =>       value * 1

2 사분면은 + 0            =>       value * 0

3 사분면은 + 32          =>       value * 2

4 사분면은 + 48          =>       value * 3

 

이런식의 값이 나오게 됩니다

 

위의 표를 보시면 (7, 7)이 해당하는 사분면의 시작 숫자 값은 48이므로 48을 더한상태로 다시 4사분면을 4개의 구역으로 나눠 줍니다

 

 

즉 8 * 8 크기의 (7, 7)의 값을 구하는 과정은

48이라는 value값 + 4 * 4 크기의 (3, 3)의 값을 구하는 과정과 같습니다.

 

 

이렇게 보시면 4 * 4의 (3, 3)은 또 4사분면에 해당합니다.

 

4 * 4 크기의 (3, 3)지점에 해당하는 value값은 12에 해당하므로

 

48을 더한 상태로 표를 그리면 밑의 처럼 표가 완성됩니다.

 

8 * 8 크기의 (7, 7) 지점의 값은

 

48 + 12 +      2 * 2 크기의 (1, 1)에 해당하는 값 이므로 3이라는 값이 나오게 됩니다.

2 * 2의 크기는 N이 1일 때 가능하기 때문에 위의 코드처럼 구현되어 있습니다.

 

48 + 12 + 3 으로

63이라는 값이 나오게 됩니다.

표를 보면 값이 같습니다.

 

 

 

최종적으로 이 문제는 큰 틀로 4등분을 해서 구역을 나눈다음 그 구역에 해당하는 좌표값을 찾습니다.

 

그리고 좌표가 해당하는 사분면에서 그 좌표가 한변의 길이의 절반값 보다 크다면 빼거나 나머지를 사용해줍니다.

 

ex) 8 * 8 크기의 (7, 7)좌표      =>      4 * 4 (3, 3)                  7 % 4  또는  7 - 4     똑같이 3이라는 값이 나오게됩니다.

 

이런식으로 큰 구역에서 작은 구역으로 들어가다 보면 2 * 2라는 값이 나오고 이 값에서 더 이상 재귀함수를 호출하지 않고

 

값만 리턴하기 때문에 재귀함수 하나가 value + value + ... + value + (0 or 1 or 2 or 3) 값이 최종적으로 나오게 됩니다.