[알고리즘] 백준 1074 Z -분할정복- 자바

www.acmicpc.net/problem/1074

1074번: Z

 

solved.ac 에서 레벨에 맞는 문제를 골라서 가끔 풀고있습니다.

그 중 한 문제입니다. 풀고서 다른 분들의 풀이를 봤는데 다양하게 푸는 것 같고 효율성 관련하여 에러가 난다는 말씀이 많았습니다. 문제를 제출하고 45초 동안이나 테스트케이스를 돌리는걸 보니 효율성이 중요한 듯 합니다.

 

저는 분할정복을 사용하여 문제를 해결했습니다.

4분의 1조각 씩 쪼개면서 2x2(num이 2일때) Z모양으로 탐색을 해주며 횟수를 증가시켜 나가면 됩니다.

 

풀이는 다음과 같습니다. 

 

[Java]

import java.util.Scanner;

class Main {
    private static int r;
    private static int c;
    private static int n;
    private static int count;
    private static int[] dx = {0, 1, 0, 1};
    private static int[] dy = {0, 0, 1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = (int)Math.pow(2, sc.nextInt());
        r = sc.nextInt();
        c = sc.nextInt();
        dfs(n, 0, 0);
    }

    private static void dfs(int num, int row, int col) {
        if(num == 2 ) {
            for (int i = 0; i < 4; i++) {
                int r2 = row + dy[i];
                int c2 = col + dx[i];
                if (r2 == r && c2 == c) {
                    System.out.println(count);
                    System.exit(0);
                }
                count++;
            }
            return;
        }
        dfs(num / 2, row, col);
        dfs(num / 2, row, col + num / 2); //우측
        dfs(num / 2, row + num / 2, col);  //하단
        dfs(num / 2, row + num / 2, col + num / 2); //대각선하단
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!