[백준/BOJ 1074] Z (Java)

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

1074번: Z

규칙성을 발견하는게 쉬우면서 어려웠다.

4개의 구역으로 쪼개진 영역을 재귀적으로 방문하는 형식으로 값을 구하면 되겠지 싶었다.

이동볌위는 결국 현재 재귀의 깊이에서 2^N-1만큼 발생하기 때문에

이동하는 값을 1까지 줄여놓는다면 ( 2^0 ) 한칸씩 움직이는 형태로 쪼개낼 수 있다고 생각했다.

또한 재귀 시 파라미터로 필요한 값은 x, y좌표 그리고 현재 재귀에서 이동할 가중치 값이 필요로 했다.

N이 2일 경우 무브먼트

예를 들어, N이 2일 경우 

색이 다른 네 구간으로 쪼개지고 이동을 하게 된다. 이 구간들을 이동하는 가중치는

빨간 화살표 -> 2만큼 추가되고, 파란 화살표에서도 2만큼, 초록색 화살표에서도 2만큼 추가된다. 

2의 1제곱, 즉 2의 (N-1)제곱만큼 가중치가 부여되는 것을 확인 할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num1074 {
  private static int r;
  private static int c;
  private static int n;
  private static int cnt = 0;
  private static int x = 0;
  private static int y = 0;
  private static int[][] board;

  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    n = Integer.parseInt(st.nextToken());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());
    int num = (int) Math.pow(2,n);
    board = new int[num][num];
    dfs(num, 0, 0);
    System.out.println(board[r][c]);
  }

  private static void dfs(int num, int x, int y) {
    if (num == 1){
      board[y][x] = cnt++;
      return;
    }
    int half = num / 2;
    dfs(half, x, y);
    dfs(half, x + half, y);
    dfs(half, x, y + half);
    dfs(half, x + half, y + half);
  }
}

테스트 케이스도 정상적으로 동작하는 것으로 보아 정답일 것이라고 생각했으나

충격적인 OOME의 현장

바로 메모리 초과로 컽 당했다.

이유는 값을 기록하는 판으로 사용한 int배열 board에 있었다. 

반례는 아주 쉽게 찾아볼 수 있었는데, 15x15짜리 2차원 배열 만드니까 바로 OOME나와서 빠른 인정 후 다른 방법을 모색했다.

메모리가 문제? 그렇다면 한단계 발전해서 아예 기록판을 안쓰고 값만 더해 올리고 해당 좌표만 기억한 상태로 입력값과 맞는지 비교만 하면 되지 않을까? 하고 천재적인 발상에 무릎을 탁 친 후 코드를 수정했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num1074 {
  private static int r;
  private static int c;
  private static int n;
  private static int cnt = 0;
  private static int res = 0;

  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    n = Integer.parseInt(st.nextToken());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());
    int num = (int) Math.pow(2,n);
    dfs(num, 0, 0);
    System.out.println(res);
  }

  private static void dfs(int num, int x, int y) {
    if (num == 1){
      cnt++;
      if(y == r && x == c) res = cnt -1;
      return;
    }
    int half = num / 2;
    dfs(half, x, y);
    dfs(half, x + half, y);
    dfs(half, x, y + half);
    dfs(half, x + half, y + half);
  }
}

코드에서 -1을 해주는 것은 끝까지 전부 계산했을 경우 1이 추가로 더해지기 때문에 빼주었다.

그리고 실행한 결과

이게뭐야

바로 시간초과로 한번 더 컽 당했다. 

반례는 다시 간단했다 똑같이 15x15짜리 배열에 1024행 1024열 값을 가져오는 테스트 케이스를 실행하였더니

제한시간인 0.5초보다 한참 더걸려서 빠른 수긍 후 다음 방법을 생각했다.

결국에 재귀의 깊이가 너무 깊어진다는 것과 생각해보면 행과 열을 이미 알고 있는데 그 전에 행열은 이미 방문한것 아닌지라는 생각이 떠올랐다.

쪼개지는 블록안에 내가 알고자 하는 좌표가 없다면 방문한 것으로 하고 값을 더해 버리면 되시겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Num1074 {
  private static int r;
  private static int c;
  private static int n;
  private static int cnt = 0;
  private static int res = 0;

  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    n = Integer.parseInt(st.nextToken());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());
    int num = (int) Math.pow(2,n);
    dfs(num, 0, 0);
    System.out.println(res);
  }

  private static void dfs(int num, int x, int y) {
    if (y == r && x == c){
      res = cnt;
    }
    if (num == 1){
      cnt++;
      return;
    }
    if(!(y<=r && r<y+num && x<=c && c<x+num)){
      cnt += num*num;
      return;
    }
    int half = num / 2;
    dfs(half, x, y);
    dfs(half, x + half, y);
    dfs(half, x, y + half);
    dfs(half, x + half, y + half);
  }
}

문제의 반례 15 1024 1024도 빠르게 나오는것을 확인 후 제출하였고

1074번 컽