[백준(Baekjoon)][자바(java)] 1074 : Z / 재귀

 

www.acmicpc.net/problem/1074

1074번: Z

 

문제

 

크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

 

 

문제 풀이

 

▶  한 칸 한 칸 방문  --> 재채점 되면서 시간 초과

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

public class Main {
	
	static int cnt;
	
	public static void recursion_z( int x, int y, int n, int r, int c ) {
		if( n == 1 ) {
			if( x == r && y == c )
				System.out.println( cnt );
			cnt++;
			return;
		}
		int m = n/2;
		recursion_z( x, y, m, r, c );
		recursion_z( x, y+m, m, r, c );
		recursion_z( x+m, y, m, r, c );
		recursion_z( x+m, y+m, m, r, c );
	}

	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() );
		n = (int)Math.pow( 2, n );
		recursion_z( 0, 0, n, r, c );

	}
}

 

* 재귀 + 분할정복

문제에서 "N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다." 라는 조건을 적용

2^(N-1) == N/2

현재 좌표 (x, y)와 n, r, c를 매개 변수로 하는 함수 안에서 n을 2로 나눠가며 재귀호출 하고, n == 1 이 되면 방문순서를 더하고 리턴하며( 재귀 함수의 기저 사례( base case ) ), 현재 좌표가 (r, c)일 경우 방문순서를 출력한다.

 

 

▶  사분면 방문

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

public class Main {
	
	public static void recursion_z( int n, int r, int c, int o ) {
		if( n == 0 ) {
			System.out.println( o );
			return;
		}
		int l = (int)Math.pow( 2, n-1 );
		if( r < l && c < l ) 		recursion_z( n-1, r, c, o );
		else if( r < l && c >= l ) 	recursion_z( n-1, r, c-l, o + (l*l) );
		else if( r >= l && c < l ) 	recursion_z( n-1, r-l, c, o + (l*l)*2 );
		else 						recursion_z( n-1, r-l, c-l, o + (l*l)*3 );
	}

	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() ),
		r = Integer.parseInt( st.nextToken() ),
		c = Integer.parseInt( st.nextToken() );
		br.close();
		recursion_z( n, r, c, 0 );
	}
}