[BOJ] 1074번 Z

개요

Z모양으로 탐색하는 문제

입력의 크기가 최대 2^15이나 되기 때문에 배열없이 풀어야 한다.

문제링크

코드

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

public class Baekjoon1074 {
    public static int count = 0;
    public static int r;
    public static int c;
    public static int result = -1;
    public static void main(String[] args) 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 = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        z(n,0,0);

        bw.write(result+"\n");
        bw.flush();
        
    }

    public static void z(int n, int row, int col) {
        int N = (int)Math.pow(2, n);
        if(r == row && c == col) {  //답에 도달했으면 카운트값 저장
            result = count;
            return;
        }

        if(r >= row && r < row+N && c >= col && c < col+N) { 
            z(n-1, row, col);               //왼쪽 상단
            z(n-1, row, col+(N/2));         //오른쪽 상단
            z(n-1, row+(N/2), col);         //왼쪽 하단
            z(n-1, row+(N/2), col+(N/2));   //오른쪽 하단
        }
        else {  //이 범위안에 해당좌표가 없으면
            count += N*N;
        }
    }
}

해결 과정

맨처음에는 2차원 배열을 선언해서 배열에 한칸한칸 카운트를 세주면서 하도록 코드를 작성하였다.

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

public class Main {
    public static int[][] arr;
    public static int count = 0;
    public static void main(String[] args) 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 = Integer.parseInt(st.nextToken());
        int N = (int)Math.pow(2, n);
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        arr = new int[N][N];

        z(n,0,0);

        bw.write(arr[r][c]+"\n");
        bw.flush();
        
    }

    public static void z(int n, int row, int col) {
        int N = (int)Math.pow(2, n);
        if(n == 1) {
            for(int i =row;i<row+2;i++) 
                for(int j=col;j<col+2;j++) 
                    arr[i][j] = count++;
        }
        else {
            z(n-1, row, col);               //왼쪽 상단
            z(n-1, row, col+(N/2));         //오른쪽 상단
            z(n-1, row+(N/2), col);         //왼쪽 하단
            z(n-1, row+(N/2), col+(N/2));   //오른쪽 하단
        }
    }
}

작은 입력값은 상관없지만 이렇게 되면 입력값의 최대크기인 2^15에서 메모리초과가 나버린다.

그렇다면 배열 없이 카운트를 효과적으로 계산하여 작성해야 한다는 말인데

N-Queen문제를 풀 때처럼 노드의 유망성을 확인하는 방식으로 다시 작성하였다.

탈출조건이 안되면 4개의 재귀함수로 들어가는 건 똑같지만 해당 깊이에 정답좌표가 포함되지 않으면 바로 나오도록 했다.

위 사진은 어떤식으로 카운트를 세는지 나타낸다.

만약에 빨간점에 해당하는 (6,7)좌표가 입력으로 주어지면 해당좌표가 포함되지 않은 부분은 바로 크기만큼 카운트 하면서 해당좌표가 나올 때까지 탐색한다.

그림에서는 16+16+16+4+4+4+1 = 61이라는 답이 나온다.

결과