[BOJ/Java] 1074. Z

[BOJ/Java] 1074. Z

1074번: Z

---

문제 해석

이 문제는 2의 거듭제곱으로 정의된 2차원 배열에서 특정 위치의 방문 순서를 Z-모양 순회로 찾는 것이 목표다. Z-모양 순회는 배열을 4분할하여 각 분할을 재귀적으로 순회하는 방식으로 진행된다.

풀이 과정

제출된 Java 코드는 분할 정복 알고리즘을 활용하여 주어진 위치 (r, c)의 방문 순서를 계산한다. 큰 배열을 작은 단위로 분할하면서 해당 위치가 포함된 분할만을 추가로 탐색하는 방식을 사용한다.

 

• 데이터 입력: n, r, c를 입력받아 n은 2의 거듭제곱으로 변환된 배열의 크기를 나타낸다.
• 분할 정복 (division 메소드): 배열을 네 부분으로 나누고, 각 부분에 대해 재귀적으로 같은 과정을 반복한다. 타겟 위치가 포함된 부분만 탐색하고, 그렇지 않은 부분은 순서를 건너뛴다.

코드

package edu.ssafy.im.BOJ.Silver.S1.No1074;

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

public class Main {
    private int ans = 0; // 타겟 위치까지의 카운트
    private int r, c; // 타겟 위치의 행과 열
    private StringBuilder sb = new StringBuilder(); // 출력을 위한 StringBuilder

    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = (int) Math.pow(2, Integer.parseInt(st.nextToken())); // 배열의 크기
        r = Integer.parseInt(st.nextToken()); // 행 위치
        c = Integer.parseInt(st.nextToken()); // 열 위치

        division(n, 0, 0); // 분할 정복 시작

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void division(int n, int x, int y) {
        if (x == r && y == c) { // 타겟 위치에 도달한 경우
            System.out.println(ans);
            return;
        }

        if (n == 1) { // 더 이상 분할할 수 없는 경우
            ans++;
            return;
        }

        if (x > r || y > c || x + n <= r || y + n <= c) { // 타겟 위치가 현재 분할에 없는 경우
            ans += n * n;
            return;
        }

        n /= 2; // 크기를 반으로 줄임
        division(n, x, y); // 왼쪽 위
        division(n, x, y + n); // 오른쪽 위
        division(n, x + n, y); // 왼쪽 아래
        division(n, x + n, y + n); // 오른쪽 아래
    }
}

시간 복잡도 분석

이 알고리즘은 분할 정복을 사용하므로, 각 분할마다 문제의 크기가 절반으로 줄어든다. 최악의 경우, 순회 경로가 한 쪽 끝에서 반대쪽 끝으로 진행되어도 시간 복잡도는 O(logN)으로 효율적이다.

느낀점

이 문제를 통해 큰 데이터를 효율적으로 처리하는 분할 정복 기법의 중요성을 이해할 수 있었다. 큰 문제를 작은 문제로 나누어 해결하는 방식은 다양한 알고리즘 문제에서 광범위하게 활용되며, 특히 배열과 관련된 문제에서 그 효율성이 두드러진다.