HS_development_log

백준 1074번 - Z / Java 본문

Algorithm-백준/분할정복

백준 1074번 - Z / Java

DevHyeonseong 2020. 2. 3. 19:53
반응형

문제

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

 

1074번: Z

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r,

www.acmicpc.net

재귀적 탐색으로 문제를 작게 쪼개서 풀면되는문제.

 

알고리즘

  1. 4칸이 될때까지 재귀함수를 사용하여 쪼개서 들어간다

  2. 4칸이되면 Z순서대로 탐색을 한다. 탐색중 r과c의 인덱스가 나오면 현재 번호를 출력한다

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * BOJ1074
 * 2020.02.03
 * Hyeonseong 
 */
import java.util.*;    
public class BOJ1074 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    int n,r,c;
    int num;
    public Solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        r = scan.nextInt();
        c = scan.nextInt();
        num = 0;
        solve(0,0,(int)Math.pow(2,n));
    }
    public void solve(int x, int y, int n) {
        int m = n/2;
        if(m==1) {
            for(int i=0;i<2;i++) {
                for(int j=0;j<2;j++) {
                    if(x+i==r && y+j ==c) { // 원하는 인덱스가 오면 순서 출력후 종료
                        System.out.println(num);
                        System.exit(0);
                    }
                    num++; // 4칸짜리가 되면 순서기록
                }
            }
            return;
        }
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                solve(x+i*m,y+j*m,m); // 4칸이될때까지 쪼갠다
            }
        }
    }
}
cs

 

 

반응형

'Algorithm-백준 > 분할정복' 카테고리의 다른 글

백준 2263번 - 트리의 순회 / Java  (0) 2020.02.03
백준 1780번 - 종이의 개수 / Java  (0) 2020.02.03
백준 11728번 - 배열 합치기 / Java  (0) 2020.02.03
'Algorithm-백준/분할정복' Related Articles more