초보개발자.. 2021. 6. 9. 11:45

--문제--

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

 

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서

www.acmicpc.net

--문제 접근--

처음 문제를 봤을 때에 DFS로 풀어야겠다는 생각을 들고 DFS의 특성을 이용하여 계속 안쪽으로 들어가는 특성을 이용하여 풀이를 진행하였습니다.

package Class3;

import java.util.Scanner;

public class BOJ_1074_Z {
	static int n,r,c,cnt;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		r=sc.nextInt();
		c=sc.nextInt();
		
		int size=(int)Math.pow(2,n);
		cnt=0;
		dfs(size,r,c);
		System.out.println(cnt);
	}
	private static void dfs(int size, int r2, int c2) {
		if(size==1)return;
		if(r2<size/2&& c2<size/2)dfs(size/2,r2,c2);//1사분면
		else if(r2 < size/2 && c2 >= size/2) {//2사분면
			cnt += size * size / 4;
			dfs(size/2, r2, c2 - size/2);
		}
		else if(r2 >= size/2 && c2 < size/2) {//3사분면
			cnt += (size * size / 4) * 2;
			dfs(size/2, r2 - size/2, c2);
		}
		else {//4사분면
			cnt += (size * size / 4) * 3;
			dfs(size/2, r2 - size/2, c2 - size/2);
		}

	}
}