[백준] 1074번: Z - JAVA

🔗 문제 링크

BOJ 1074번:Z

1074번: Z

 

📝 풀이 과정

N = 2일 때의 탐색 모형이다.

처음 큰 $2^2$ x $2^2$의 사각형을 4등분으로 분할한 뒤 Z모양으로 탐색하고, $2^1$ x $2^1$을 Z모향으로 탐색을 하게 되면 위와 같은 그림이 나오게 된다.

 

처음 문제를 봤을 때, 단순 분할 + 재귀 문제라고 생각하고 모든 칸을 방문하며 count 했고, 실패했다...

 

시간 복잡도를 잘 따지지 않아 생겼던 문제인데, N의 범위는 1 <= N <= 15이다. 따라서, 최대 사각형의 크기는 $2^{15}$ x $2^{15}$ 로 $2^{30}$ 이 된다! 대략 10억정도의 숫자이므로 제한시간을 엄청 뛰어 넘어버리게 된다.

 

다시 생각한 방법은 어차피 분할하게 되더라도 크기를 알기 때문에 굳이 하나씩 탐색할 필요가 없음을 알게 되었다. 찾기 원하는 좌표 밖에 있는 사각형은 무조건 끝까지 탐색하게 되므로, 탐색을 하지 않고 그냥 해당 칸의 크기만큼 + 해주면 된다는 것이다.

⭐가 그려진 곳이 찾아가야 하는 목적지라면 회색의 표시된 부분은 굳이 탐색할 필요없이 각 사각형의 크기인 4 만큼을  count에 더해주면 되는 것이다. 만약 범위를 조사해 목적지가 찾는 범위 내에 존재한다면, 다시 분할하며 목적지를 찾아가도록 한다.

 

💻 코드

import java.util.Scanner;

public class Main {
    static int N, r, c, cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        r = sc.nextInt();
        c = sc.nextInt();

        solve((int) Math.pow(2, N), 0, 0);
    }

    static void solve(int n, int y, int x) {
        if (y == r && x == c) {
            System.out.println(cnt);
            System.exit(0);
        }

        if (y <= r && r < (y + n) && x <= c && c < (x + n)) {
            int nn = n / 2;
            solve(nn, y, x);
            solve(nn, y, x + nn);
            solve(nn, y + nn, x);
            solve(nn, y + nn, x + nn);
        } else
            cnt += n * n;
    }
}

 

📊 제출 결과