백준 1074번 : Z (JAVA) 문제 풀이

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

1074번: Z

---

 

✏️ 문제

 

🔐 문제 해결

주의! 이 문제는 하나 하나 탐색하여 DFS를 시도하면 시간초과되어 통과할 수 없게 된다.

아래는 시간 초과 받은 풀이..ㅠ

시간 초과 받은 풀이이다.

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

public class Main {
    static int N, r, c;
    static int count;
    static int[][] arr;
    static int[] dx, dy;

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        // 변수 초기화 작업
        count = 0;
        /**
         * dx[], dy[] 의 역할 가장 작은 2X2 배열의 방문을 위해
         *      - 예를들어, 2X2 배열의 각 시작점은 다음과 같다.
         *      (0,0) -> (0,1) -> (1,0) -> (1,1)
         */
        dx = new int[]{0, 0, 1, 1};
        dy = new int[]{0, 1, 0, 1};

        // 입력
        int n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        N = (int) Math.pow(2, n);
        // arr = new int[N][N];

        // 길이가 N이고 시작점의 좌표 x, y를 넣어서 재귀 호출 시작!
        recur(N, 0, 0);
    }

    static void recur(int len, int x, int y) {
        // 종료 조건 : 가장 작은 길이 2X2 배열이 되었을 때!

        if (len == 2) {
            // 이전에 만들어둔 dx[], dy[] 배열을 이용해서 방문횟수 기록!
            for (int i = 0; i < 4; i++) {
                int nX = x + dx[i];
                int nY = y + dy[i];

                count++;
                if(nX == r && nY == c){
                    System.out.println(count - 1);
                    System.exit(0);
                }
            }
            return;
        }

        // 길이가 4가 넘는다면, 계속 분할하도록 한다.
        if (len >= 4) {
            /**
             * 아래 재귀 호출에 대해 설명
             *      - 4X4 배열의 4개의 2X2 배열의 시작점을 다음과 같다.
             *          - (0,0) -> (0,2) -> (2,0) -> (2,2)
             *              - ex) x + len/2 또는 y + len/2
             */
            recur(len / 2, x, y);
            recur(len / 2, x, y + len / 2);
            recur(len / 2, x + len / 2, y);
            recur(len / 2, x + len / 2, y + len / 2);
        }
    }
}

 

일정한 패턴이 재귀적으로 반복되기 때문에 r행 c열이 어느 사분면에 위치하고 몇번째로 방문했는지  알 수 있기 때문에 해당 방법으로 풀이를 해보도록 하겠다.

 

일단, 이 문제는 가장 작은 단위가 2X2 배열이다.

 

아래 4X4 배열을 살펴 보자

4X4 배열을 보면, 가장 작은 단위인 2X2 배열이 총 4개가 연속된다는 것을 알 수 있다.

 

각 2X2 배열의 시작 인덱스를 살펴보면 다음과 같다.

1. (0 , 0)
2. (0 , 2)
3. (2 , 0)
4. (2 , 2)

현재 길이가 N이고 시작 인덱스가 (x , y) 라고 할 때, 위에 인덱스를 식으로 표현하면 다음과 같다.

(x , y)
(x , y + N/2)
(x + N/2 , y)
(x + N/2 , y + N/2)

일정한 패턴이 보이고 있다.

이 시작 위치를 이용해서 해당 r행 c열이 어느 사분면에 위치하는지 범위를 계속해서 좁혀나가면서 찾아내면 된다!

 

예를 들어, 4X4 배열에서 (1 , 2) 가  어느 사분면에 있는지 함께 찾아보도록 해보자.

우리가 (2 , 1)을 찾는 다면? 아래의 방법으로 찾을 수 있다.

• 시작점의 왼쪽 위 꼭지점 (x , y) 고 길이가 len일 때, 각 사분면의 왼쪽 위 꼭지점과 오른쪽 아래 꼭지점은 다음과 같이 구할 수 있다.
• 어느 사분면인지 찾았다면 len이 2가 될때까지 해당 작업을 반복하면 된다.

int[] dx = {0, 0, 1, 1};
int[] dy = {0, 1, 0, 1};

// 시작점이 (x , y) 라고 할 때! 각 사분면의 시작점과, 끝점을 아래와 같이 구할 수 있다.
for (int i = 0; i < 4; i++) {
    int nX1 = x + len / 2 * dx[i];
    int nX2 = x + len / 2 * (dx[i] + 1) - 1;
    int nY1 = y + len / 2 * dy[i];
    int nY2 = y + len / 2 * (dy[i] + 1) - 1;

	// 해당 사분면 범위에 들어온다면? -> 현재 i가 r,c가 속한 사분면이다!
    if (r >= nX1 && r <= nX2 && c >= nY1 && c <= nY2) {
        count = count + (len / 2 * len / 2 * i);	// *방문 횟수를 카운트!
        recur(len/2, nX1, nY1);	// 해당 사분면의 길이를 반으로 나눠서 다시 탐색!
    }
}

위 코드에서 count = count + ( len / 2 * len / 2 * i); 라는 코드를 보면, 각 사분면의 방문횟수는 아래의 그림처럼 나타낼 수 있다.

 

종료 조건은 길이가 2가 될 때 종료시키면 된다.

• 해당 사분면에서 Z 방향으로 탐색
  • count 1씩 증가시킨다.
  • 행과 열이 r, c와 같아지는 시점에서 count를 출력시키면 끝!

static void recur(int len, int x, int y) {
    
    // 종료 조건 : 가장 작은 길이 2X2 배열이 되었을 때!
    if (len == 2) {
        // 이전에 만들어둔 dx[], dy[] 배열을 이용해서 방문횟수 기록!
        for (int i = 0; i < 4; i++) {
            int nX = x + dx[i];
            int nY = y + dy[i];
            count++;
            if (nX == r && nY == c) {
                System.out.print(count - 1);	// 정답은 1을 빼주도록 한다.
                System.exit(0);
            }
        }
        return;
    }
    
    ...

}

 

 

🖥 전체 코드

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

public class Main {
    static int N, r, c;
    static int count;
    static int[][] arr;
    static int[] dx, dy;

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        // 변수 초기화 작업
        /**
         * dx[], dy[] 의 역할 가장 작은 2X2 배열의 방문을 위해
         *      - 예를들어, 2X2 배열의 각 시작점은 다음과 같다.
         *      (0,0) -> (0,1) -> (1,0) -> (1,1)
         */
        dx = new int[]{0, 0, 1, 1};
        dy = new int[]{0, 1, 0, 1};

        // 입력
        int n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        N = (int) Math.pow(2, n);
        // arr = new int[N][N];

        // 길이가 N이고 시작점의 좌표 x, y를 넣어서 재귀 호출 시작!
        recur(N, 0, 0);
    }

    static void recur(int len, int x, int y) {
        // 종료 조건 : 가장 작은 길이 2X2 배열이 되었을 때!

        if (len == 2) {
            // System.out.println(x + " , " + y);
            // 이전에 만들어둔 dx[], dy[] 배열을 이용해서 방문횟수 기록!
            for (int i = 0; i < 4; i++) {
                int nX = x + dx[i];
                int nY = y + dy[i];

                count++;
                if (nX == r && nY == c) {
                    System.out.print(count - 1);
                    System.exit(0);
                }
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nX1 = x + len / 2 * dx[i];
            int nX2 = x + len / 2 * (dx[i] + 1) - 1;
            int nY1 = y + len / 2 * dy[i];
            int nY2 = y + len / 2 * (dy[i] + 1) - 1;

            if (r >= nX1 && r <= nX2 && c >= nY1 && c <= nY2) {
                // System.out.println(nX1 + ", " + nY1);
                count = count + (len / 2 * len / 2 * i);
                // System.out.println("count : " + count);
                recur(len/2, nX1, nY1);
            }
        }
    }
}