[16일 차] 알고리즘 (백트래킹)

---

25/02/17 (월)

아.. 다시... 월..요..일이지만 힘내보겠습니다!

금, 토, 일을 쉬니 오히려 더 피곤한것같습니다.

주말에 술을 마시니 공부할 시간이 너무 많이 줄어서 앞으로는 안먹을까 생각중입니다..

---

2. WorkShop 발표

1) 다익스트라 알고리즘

• 가중치가 있는 최소경로
• 외워야한다

 

1.  교재 강의

1.1. Ch12 백트래킹

1) 백트래킹

• 가능성이 없는 곳에서 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘
• 유망 함수 : 해가 유망한지 아닌지를 판단할 수 있는 함수
• 가지치기(Pruning) : DFS를 통해 탐색을 하며 더 이상 필요 없는 부분을 쳐내는 행위

 

2. 실습

1) 실습

https://www.acmicpc.net/problem/9663 (해결)

https://www.acmicpc.net/problem/2239 (해결)

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

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

 

2) 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;
    }
}

생각보다 쉽게 구현했습니다

 

3) 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();
        }
    }
}

출력을 하려는데 자꾸 원본이 출력되어서 gpt한테 물어보고 풀었습니다.

백트래킹을 멈춰 줄 flag와 printSudoku를 따로 만들어야하더라고요

 

3. WorkShop

1) 알파벳

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

• 기본 시간은 1000ms 인데 조건을 수정해서 더 빠르게 가능

 

4.  마무리

1) 더 공부할 것

금요일 다익스트라, 최소신장트리

• https://www.acmicpc.net/problem/1197 
• https://www.acmicpc.net/problem/4485