[백준] no1074: Z

문제

이중배열의 지점을 Z형식으로 탐색한다.
배열의 길이는 주어진 N에 대해 2의 N승이다.

주어진 지점이 몇번째 지점인지 구해라

 

문제 링크 : https://www.acmicpc.net/problem/1074

---

원리

1. 분할 정복 재귀 : 정석

2. 분할 정복 탐색(?) : 필자는 이 방법으로 풀었음

---

풀이방법

순차적으로 카운트해주는 것이 아니다.

* 아래와 같이 해당 지점에 도달할때 까지 그 전에 나올만한 정점의 갯수를 댕겅댕겅 카운트 해주는 것이다

* 이때, 필자의 경우 해당 정점 객체에 이동한 정점의 위치와 이중배열로 나타날 면의 길이를 넣어줬다.

/**
 * 분할정복
 * 1. 주어진 길이를 2등분 하여 배열을 4등분한다
 * 2. 주어진 정점이 1사분면에 있다면 다시 4분할
 * 3. 주어진 정점이 2사분면에 있다면 1사분면을 count++ 해주고 다시 4분할
 * 4. 주어진 정점이 3사분면에 있다면 1,2사분면을 count++ 해주고 다시 4분할
 * 5. 주어진 정점이 4사분면에 있다면 1,2,3사분면을 count++ 해주고 다시 4분할
 * 6. 길이가 1이 될 때까지 4분할 진행
 */

---

나의 코드

/**
 * 결과를 카운트 해줄 변수
 */
private static int count;

/**
 * 입력, 실행 및 출력을 담당하는 main메소드
 */
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int Length = (int) Math.pow(2, Integer.parseInt(st.nextToken()));
    int X = Integer.parseInt(st.nextToken());
    int Y = Integer.parseInt(st.nextToken());

    Quad(X, Y , Length);

    System.out.println(count);
}

/**
 * 실질적으로 값을 계산해주는 로직이 담긴 메소드
 * @param X,Y : 주어진 최초의 지점의 위치
 * @param Length : 주어진 최초의 이중배열의 길이 
 */
private static void Quad(int X, int Y, int Length) {
    Deque<Node> dq = new ArrayDeque<>();
    dq.add(new Node(X,Y,Length));  // 첫번째 계산을 위함

    // 1이 되기 전까지 대기열에 계산해줄 값이 Node 객체 형식으로 담길거임
    while(!dq.isEmpty()) {
        Node now = dq.poll();
        int nowX = now.X;
        int nowY = now.Y;
        int nowL = now.L;

        // 1이면 마지막 지점이므로 더이상 대기열에 넣지 않음
        if(nowL!=1) {
            // 1 사분면
            if (nowX < nowL/2 && nowY < nowL/2) {
                dq.add(new Node(nowX, nowY, nowL/2));
            }
            // 2 사분면
            else if (nowX < nowL/2 && nowY >= nowL/2) {
                count += ((nowL/2) * (nowL/2));
                dq.add(new Node(nowX, nowY-nowL / 2, nowL/2));
            }
            // 3 사분면
            else if (nowX >= nowL / 2 && nowY < nowL / 2) {
                count += ((nowL/2) * (nowL/2)) * 2;
                dq.add(new Node(nowX-nowL / 2, nowY, nowL / 2));
            }
            // 4 사분면
            else {
                count += ((nowL/2) * (nowL/2)) * 3;
                dq.add(new Node(nowX-nowL/2, nowY-nowL/2, nowL/2));
            }
        }
    }
}

private static class Node {
    private int X;
    private int Y;
    private int L;
    public Node(int x, int y, int L) {
        this.X = x;
        this.Y = y;
        this.L = L;
    }
}