[BOJ] 1074 Z java

문제

한수는 크기가 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 ≤ N ≤ 15
• 0 ≤ r, c < 2N

풀이

package baekjoon;

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

public class BOJ1074 {

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

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int n, r, c, len, cnt, ans;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        r = stoi(st.nextToken());
        c = stoi(st.nextToken());
        len = (int) Math.pow(2, n);

        //로직
        recur(len, 0, 0);

        System.out.println(ans);
    }

    static int stoi(String s) {return Integer.parseInt(s);}

    static void recur(int len, int x, int y) {
        if (len == 2) {
            for (int i = 0; i < 4; i++) {
                x += dx[i];
                y += dy[i];

                if (x == r && y == c) {
                    ans = cnt;
                    return;
                }
                cnt++;
            }
            return;
        }

        int nextLen = len / 2;
        int sumCnt = (int) Math.pow((double)len / 2, 2);

        if (x + nextLen - 1 >= r && y + nextLen - 1 >= c) {
            recur(nextLen, x, y);
        }
        else if (x + nextLen - 1 >= r) {
            cnt += sumCnt;
            recur(nextLen, x, y + nextLen);
        }
        else if (y + nextLen - 1 >= c) {
            cnt += sumCnt * 2;
            recur(nextLen, x + nextLen, y);
        }
        else {
            cnt += sumCnt * 3;
            recur(nextLen, x + nextLen, y + nextLen);
        }
    }
}

 

재귀를 활용한 구현문제였다.

 

전체 크기의 2차원 배열을 계속 4등분 해주고 더이상 나눌 수 없을 때 z자로 순서를 구해주었다.

 

처음에 모든 4분면을 방문해서 [r,c] 번 째에 방문했을 경우 return 해주었다. 그러고 제출하니 시간초과가 나왔다.

 

생각해보니 r, c의 상한이 2^15이다. 모든 2^15 * 2^15 에 방문순서를 구하면 당연히 시간초과가 나온다.

 

이부분을 먼저 고려하면서 구현했어야 했는데 그러지 못했다. 그래서 질문 게시판을 보니 r, c가 속한 분면만 구하면 

 

되는 것이었다. 그래서 해당 분면에 들어갈 때 cnt값들을 구해서 더해주면서 구해주었다.