[Boj_1074] Z

📎 문제 링크

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

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

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 1
• 🔔  문제 유형 : 분할 정복, 재귀
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

앞서 포스팅했던 색종이 만들기, 쿼드트리 문제와 유사하지만

N의 범위가 최대 15이므로 2^15 사이즈의 map을 모두 작게 분할해 r, c를 하나씩 확인한다면 시간초과가 난다.

그렇기 때문에, 먼저 r, c가 1, 2, 3, 4 사분면 중 어느 사분면에 속해있는지 체크해 주고,

r, c가 속해있는 사분면에서만 재귀를 돌려주었다.

 

예를 들어 size = 4인 이차원 배열이 있고, r = 1, c = 1의 값을 찾는다고 하자

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

(1, 1)은 1 사분면에 있고, size/2로 1 사분면에 대한 재귀를 타면

0	1
2	3

위와 같이 size = 2인 사분면으로 또 나뉜다.

여기서 (1, 1)은 4 사분면에 있고, 다시 size/2로 사분면에 대한 재귀를 타면

3

size = 1인 1 사분면 값만 남게 된다.

이때 1 사분면의 값인 3이 정답이 되고, size = 1일 경우 return 조건이 된다.

 

그럼 1, 2, 3, 4 사분면의 범위에 대한 if 조건문이 각각 있고, 그때마다 이차원 배열에 들어갈 값을 구해주어야 한다.

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

먼저, 이차원 배열이기 때문에 size가 4일 경우 16가지의 숫자가 들어가고, 시작이 0부터이므로 0~15까지의 숫자가 들어있다.

이때 만약, 2 사분면에 재귀를 탄다고 하면, 1 사분면의 0~3을 세어주고 4부터 값이 시작해야 한다.

3 사분면의 재귀를 탄다고 하면, 1 2 사분면의 0~7을 세어주고 8부터 값이 시작된다.

따라서 각 사분면의 0, 4, 8, 12가 해당 사분면의 시작값이 된다.

 

2 사분면 : (size* size)/4

3 사분면 : ((size* size)/4) * 2

4 사분면 : ((size* size)/4) * 3

 

각 재귀에서 위와 같이 계산하여 시작값을 더해주면 된다.

 

✔ 최종 코드

메모리 : 11636KB
시간 : 84ms

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

public class Main {
    static int n, r, c;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 2N × 2N
        // r행 c열을 몇 번째로 방문
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int size = (int)Math.pow(2, n); // 한 변의 길이

        partition(0, 0, size); // 시작점, 한 변의 길이
        bw.append(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void partition(int x, int y, int size) {
        // 더 이상 분할 불가능
        if (size == 1) return;

        // r행 c열이 몇 사분면에 있는지 체크
        int newSize = size/2;
        // 1 사분면에 있다면 절반으로 분할해서 재귀 (r행 c열이 어디에 위치하는지 다시 확인)
        if (r < x+newSize && c < y+newSize) partition(x, y, newSize);
        // 2 사분면에 있다면
        if (r < x+newSize && c >= y+newSize) {
            ans += (size*size) / 4; // ex) size = 2일때, 2사분면이 1번째 방문
            partition(x, y+newSize, newSize);
        }
        // 3 사분면에 있다면
        if (r >= x+newSize && c < y+newSize) {
            ans += ((size*size) / 4) * 2;
            partition(x+newSize, y, newSize);
        }
        // 4 사분면에 있다면
        if (r >= x+newSize && c >= y+newSize) {
            ans += ((size*size) / 4) * 3;
            partition(x+newSize, y+newSize, newSize);
        }
    }
}

 

 

 

📍 함께 풀어보면 좋은 백준 문제

• 색종이  만들기
• 쿼드트리
• 별 찍기 -10

 

 

📃 reference

• https://ilmiodiario.tistory.com/140