[알고리즘 TIL] Q1074(백트래킹)

문제

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

트러블 슈팅

1. 완전탐색 구현

처음에는 완전 탐색+재귀 함수로 구현하려고 했다. 하지만, 다음 재귀함수에 어떤 값을 넘겨야할지 매우 헷갈렸다. Z 탐색은 (row, col)이 좌측 위 꼭짓점이고, 각 사분면마다 차이가 한 변의 길이/2만큼 난다. 따라서 n은 한 변의 길이여야 한다.

private static void backtracking(int row, int col, int size) throws IOException{
        if(size==1) {
            count++;
            if(row==r && col==c) {
                finishSystem();
            }
            return;
        }

        backtracking(row,col,size/2);
        backtracking(row,col+size/2,size/2);
        backtracking(row+size/2,col,size/2);
        backtracking(row+size/2,col+size/2,size/2);
    }

 

 

2. 백트래킹 구현

완전 탐색으로는 시간 초과가 났다. 이 문제는 (r,c) 좌표가 어떤 사분면에 있는지 파악해서, 해당 재귀만 돌도록 해야한다.

private static void backtracking(int row, int col, int size) {
        if (size == 1) return;

        int half = size / 2;

        if (r < row + half && c < col + half) {
            // 1사분면
            backtracking(row, col, half);
        } else if (r < row + half && c >= col + half) {
            // 2사분면
            count += half * half;
            backtracking(row, col + half, half);
        } else if (r >= row + half && c < col + half) {
            // 3사분면
            count += 2 * half * half;
            backtracking(row + half, col, half);
        } else {
            // 4사분면
            count += 3 * half * half;
            backtracking(row + half, col + half, half);
        }
    }

구현

import java.io.*;

public class Main {

    static int N;
    static int r;
    static int c;
    static int count = 0;
    static BufferedWriter bw;
    static BufferedReader br;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputStrArr = br.readLine().split(" ");
        N = Integer.parseInt(inputStrArr[0]);
        r = Integer.parseInt(inputStrArr[1]);
        c = Integer.parseInt(inputStrArr[2]);

        backtracking(0,0, (int) Math.pow(2, N));

        bw.write(count+" ");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void backtracking(int row, int col, int size) {
        if (size == 1) return;

        int half = size / 2;

        if (r < row + half && c < col + half) {
            // 1사분면
            backtracking(row, col, half);
        } else if (r < row + half && c >= col + half) {
            // 2사분면
            count += half * half;
            backtracking(row, col + half, half);
        } else if (r >= row + half && c < col + half) {
            // 3사분면
            count += 2 * half * half;
            backtracking(row + half, col, half);
        } else {
            // 4사분면
            count += 3 * half * half;
            backtracking(row + half, col + half, half);
        }
    }

}