[백준] 1074번 : Z - 자바(JAVA)

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

1074번: Z

 

문제 해석

크기가 2^N x 2^N인 2차원 배열을 Z 모양으로 탐색하고자 합니다.

2^1 x 2^1 방문예시

N > 1 인 경우 , 배열의 크기가 2^(N-1) x 2^(N-1)로 4등분 한 뒤에 재귀적으로 순서대로 방문합니다.

2^2 x 2^2 예시

N=3일 때 예시

2^3 x 2^3 예시

 

문제 풀이 전 설계

재귀 함수를 잘 작성해야 할 것 같다.

 

1.  r x c 배열을 생성한 후 값을 0부터 하나씩 채워가기 -> array [r][c]의 값 출력

 

2. array[r][c] = 0으로 놓고 한 칸 이동시 -1 하면서 역추적 array [0][0]에  도달하면 Math.abs(값) 출력

 

배열에 값을 채워넣으려고 했지만 배열에 값을 넣게 되면 시간이 너무 오래 걸리고 메모리 초과가 나올 수 있습니다.

 

따라서 해당 보드의 사이즈를 구하고 사이즈를 기준으로 4사분면으로 나누어 줍니다.

그리고 해당 특정 분면에 도달하게 되면 보드의 size를 /2 하며 count를 증가시킵니다.

또한 r,c 의 위치를 조정해주고 다시 재귀적으로 호출하여 size=1일 때까지 반복하게 된다면

count를 구할 수 있습니다.

 

코드

package day0215;

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

public class Main_1074_Z {
	static int count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken()); //행
		int c = Integer.parseInt(st.nextToken()); //열
		int size = (int) Math.pow(2, N); //한 변의 사이즈
		
		find(size, r, c);
		System.out.println(count);
	}

	private static void find(int size, int r, int c) {
		if(size == 1)
			return;
		
		//1사분면
		if(r < size/2 && c < size/2) {
			find(size/2, r, c);
		}
		//2사분면
		else if(r < size/2 && c >= size/2) {
			count += size * size / 4;
			find(size/2, r, c - size/2);
		}
		//3사분면
		else if(r >= size/2 && c < size/2) {
			count += (size * size / 4) * 2;
			find(size/2, r - size/2, c);
		}
		//4사분면
		else {
			count += (size * size / 4) * 3;
			find(size/2, r - size/2, c - size/2);
		}
	}
}