알고리즘문제풀이/백준
[BOJ]1074_Z_Java
초보개발자..
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);
}
}
}