[알고리즘] Part08 | 백트래킹

 

1. 백트래킹

1.1) 백트래킹

• 완전 탐색은 모든 경우의 수를 탐색하여 비효율적
• Backtracking : 가능성이 없는 곳을 알아보고 되돌아 가는 것

 

1.2) 백트래킹 알고리즘

• Backtraking Algorithm : 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘
• 문제마다 효율이 달라지므로 시간 복잡도 특정 어렵

 

1.3) 유망 함수

• Backtraking Algorithm의 핵심은 '해가 될 가능성 판단'
• 유망함수 : 그 가능성
• 백트래킹 알고리즘 진행 과정
  1. 유효한 해의 집합 정의
  2. 위 단계에서 정의한 집합 그래프로 표현
  3. 유망 함수 정의
  4. 백트래킹 알고리즘 활용하여 해 탐색

 

2. 실습

2.1) G4_9663_N-Queen

package basic.Ch19_Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class G4_9663_NQueen {
    static int N;
    static int result;
    static boolean[][] queen;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        queen = new boolean[N][N];
        result = 0;

        backtrack(0);
        System.out.println(result);
    }

    public static void backtrack(int y){
        if(y == N){
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
                if (test(y, i)) {
                    queen[y][i] = true;
                    backtrack(y+1);
                    queen[y][i] = false;
                }
        }
    }

    public static boolean test(int y, int x) {
        //위 확인
        for (int i = 0; i < y; i++) {
            if (queen[i][x]) return false;
        }

        //왼쪽 위 대각선 확인
        for (int i = 1; y - i >= 0 && x - i >= 0; i++) {
            if (queen[y - i][x - i]) return false;
        }

        //오른쪽 위 대각선 확인
        for (int i = 1; y - i >= 0 && x + i < N; i++) {
            if (queen[y - i][x + i]) return false;
        }

        return true;
    }
}

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

 

2.2) G4_2239_스도쿠

package basic.Ch19_Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class G4_2239_Sudoku {
    static int[][] arr = new int[9][9];
    static boolean flag = false;

    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 9; i++) {
            char[] c = bf.readLine().toCharArray();
            for (int j = 0; j < 9; j++) {
                arr[i][j] = c[j]-'0';
            }
        }

        backtracking(0, 0);
    }

    public static void backtracking(int y, int x){
        if(flag) return;

        if(y == 9) {
            printSudoku();
            flag = true;
            return;
        }

        int dy = (x==8) ? y+1 : y;
        int dx = (x==8) ? 0 : x+1;

        if(arr[y][x] != 0){
            backtracking(dy, dx);
            return;
        }

        for (int i = 1; i <= 9 ; i++) {
            if (func(y, x, i)){
                arr[y][x] = i;
                backtracking(dy, dx);
                arr[y][x] = 0;
            }
        }
    }

    public static boolean func(int y, int x, int num){
        int startY = (y/3)*3;
        int startX = (x/3)*3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(arr[startY+i][startX+j] == num){
                    return false;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            if(arr[y][i] == num || arr[i][x] == num){
                return false;
            }
        }
        return true;
    }

    public static void printSudoku() {
        for (int[] row : arr) {
            for (int num : row) {
                System.out.print(num);
            }
            System.out.println();
        }
    }
}

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

 

2.3) G4_1987_알파벳

package basic.Ch19_Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G4_1987_알파벳 {
    static int R, C;
    static int result;
    static char[][] arr;
    static boolean[] alpha = new boolean[26];
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];

        for (int i = 0; i < R; i++) arr[i] = bf.readLine().toCharArray();

        backtrack(0, 0, 1);
        System.out.println(result);
    }

    public static void backtrack(int y, int x, int cnt){
        result = Math.max(result, cnt);
        alpha[arr[y][x] - 'A'] = true;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny >= 0 && ny < R && nx >= 0 && nx <  C && !alpha[arr[ny][nx]-'A']){
                backtrack(ny, nx, cnt+1);
            }
        }
        alpha[arr[y][x] - 'A'] = false;
    }
}

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

 

2.4) G2_3109_빵집 (강사님 풀이)

package basic.Ch19_Backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class G2_3109_빵집 {
    // 백트래킹 - 이전에 놓은 파이프라인이 다음에 놓을 파이프라인에 영향을 미친다. ( 겹치면 X )
    // 그리디 - 최대한 많은 파이프라인....<= 왼쪽에서 오른쪽으로 이어지는 탐색 중 우선 순위 ( 우상 -> 우 -> 우하 )
    // 우선 순위대로 방문했을 때 성공하면 다음 우선순위의 탐색을 (delta) 이어가면 안되고, 바로 종료
    // 항상 현재 좌표에서 유리한 방향 1 가지만 성공하면 탐색 종료
    // visit - 특정 좌표를 탐색의 과정에서 방문하게 되면 무조건 'x' 표시 ( 현재 탐색이 성공, 실패 상관없이 )

    static int R, C, ans;
    static char[][] map;

    // delta 순서
    static int[] dy = { -1, 0, 1 }; // x 는 항상 +1, y 는 우상, 우, 우하

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][]; // String toCharArray()

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        // 각 행별로 밑으로 내려가면서 탐색 진행
        for (int i = 0; i < R; i++) {
            if( dfs(i, 0) ) ans++; //  i 번째 row 에서 왼쪽부터 오른쪽끝까지 모두 연결 성공한 경우
        }

        System.out.println(ans);
    }
    static boolean dfs(int y, int x) {

        int nx = x + 1; // 옆으로 한 칸 이동

        if( nx == C - 1 ) return true; // 빵집까지 도달

        // 우선순위를 가진 delta 다음 방문 진행
        // 다음 재귀호출의 결과가  true 이면 성공이고 이 때 다음 delta 방문 하면 X
        for (int d = 0; d < 3; d++) {
            int ny = y + dy[d];

            if( ny < 0 || ny >= R || map[ny][nx] == 'x' ) continue;
            map[ny][nx] = 'x'; // 성공해도, 실패해도 다시 방문 X
            if( dfs(ny, nx) ) return true; // 현재 좌표에서 성공
        }

        // 현재 좌표에서 성공 X
        return false;
    }
}