[백준] 13. 백트래킹 - Java 코드

https://www.acmicpc.net/step/34

백트래킹 단계

 

문제 목차

✅  1 15649  N과 M (1)
✅ 2 15650  N과 M (2)
✅ 3 15651  N과 M (3)
✅ 4 15652  N과 M (4)
✅ 5 9663  N-Queen
✅ 6 2580  스도쿠         
✅ 7 14888  연산자 끼워넣기
✅ 8 14889  스타트와 링크

대체적으로 백트레깅 문제에서는 순열과 조합을 이용한 문제가 많이 출제된다.

난이도가 올라갈수록 bfs의 개념으로 구현하는 문제가 나온다.

해당 단계에서는 5번 N-Queen, 6번 스도쿠 문제가 난이도가 있어고 재밌었기 때문에

따로 풀이 글을 작성할 예정이다.

 

 

✅  1 15649  N과 M (1)

import java.util.Arrays;
import java.util.Scanner;

public class N과M1 {
    // 중복 가능한 조합을 만드는 문제
    static int n,m;
    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();
        // 조합 출력
        Boolean[] chosen = new Boolean[n+1];
        Arrays.fill(chosen,false);
        for (int i = 1; i <= n; i++) {
            chosen[i] = true;
            comb(chosen,1,i+"");
            chosen[i] = false;
        }
    }
    // 조합 출력 
    public static void comb(Boolean[] chosen, int depth, String str){
        if(m == depth){
            System.out.println(str);
        }
        else{
            for (int i = 1; i <=n ; i++) {
                if(!chosen[i]){
                    chosen[i] = true;
                    comb(chosen,depth+1,str+" "+i);
                    chosen[i] = false;
                }
            }
        }
    }
}

 

✅ 2 15650  N과 M (2)

import java.util.Arrays;
import java.util.Scanner;
// 18,700KB, 240ms
public class N과M2 {
    // 중복 불가한 조합을 만드는 문제
    static int n,m;
    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();
        // 조합 출력
        Boolean chosen[] = new Boolean[n+1];
        Arrays.fill(chosen,false);
        for (int i = 1; i <= n; i++) {
            chosen[i] = true;
            combi(chosen,1,i+"",i);
            chosen[i] = false;
        }
    }
    // 조합 출력  (선택값체크배열,
    public static void combi(Boolean[] chosen, int depth, String str,int at){
        if(m == depth){
            System.out.println(str);
            return;
        }
        for (int i = at; i <=n ; i++) {
            if(!chosen[i]){
                chosen[i] = true;
                combi(chosen,depth+1,str+" "+i,i);
                chosen[i] = false;
            }
        }
    }
}

 

✅ 3 15651  N과 M (3)

import java.util.Scanner;
// 71,296kB , 588ms
public class N과M3 {
    // 중복가능한 순열을 만듬
    static int n,m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();
        // 순열 생성
        arr = new int[m];
        permu(0);
        // 순열 출력
        System.out.println(sb);
    }
    public static void permu(int depth){
        if(m == depth){
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
        }
        else{
            for (int i = 1; i <=n ; i++) {
                arr[depth] = i;
                permu(depth+1);
            }
        }
    }
}

 

✅ 4 15652  N과 M (4)

import java.util.Scanner;
//19,040 KB , 252ms
public class N과M4 {
    // 중복가능한 순열을 만듬
    static int n,m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sc.close();
        // 순열 생성
        arr = new int[m];
        permu(0,1);
        // 순열 출력
        System.out.println(sb);
    }
    public static void permu(int depth, int at){
        if(m == depth){
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
        }
        else{
            for (int i = at; i <=n ; i++) {
                arr[depth] = i;
                permu(depth+1,i);
            }
        }
    }
}

✅ 5 9663  N-Queen

import java.util.Scanner;

public class Main {
    static int n;
    static int cnt;
    static int[] arr;

    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sc.close();
        // 계산
        arr = new int[n];
        NQueen(0);
        System.out.println(cnt);
    }

    // N개 놓이면 count++
    // 행번호만 넣어준다.
    public static void NQueen(int depth) {
        if (n == depth) {
            cnt++;
            return;
        }
        for (int i = 0; i < n; i++) {
            arr[depth] = i; // 선택값((행)을 차례대로 넣는 배열
            if (isOk(depth)) {
                NQueen(depth + 1);
            }
        }
    }

    // 해당 자리 놓을 수 있는지 Check
    public static boolean isOk(int depth) {
        for (int i = 0; i < depth; i++) {
            if (arr[i] == arr[depth]) // 같은행의 값을 이미 가지고 있는지 체크
                return false; // 이미 저장된 행번호
            if (Math.abs(depth - i) == Math.abs(arr[depth] - arr[i]))
                return false; // 대각선상에 놓인 번호 check
        }
        return true;
    }
}

 

✅ 6 2580  스도쿠

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
// 26,096 KB , 512ms
public class 스도쿠 {
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        // 입력과 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[9][9];
        //int n = 0; // 구해야 하는 정답 수
        for (int i = 0; i < 9; i++) {
             int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
             //n += Arrays.stream(tmp).filter(val->val==0).count();
             arr[i] = tmp;
        }
        br.close();
        // 함수 시작
        sudoku(0,0);

    }
    public static void sudoku(int row,int col){
        if(col == 9) { // 0~8까지 돌았으면 0으로 시작
            sudoku(row + 1, 0);
            return;
        }if(row ==9) {// 정답을 찾았다면, 답을 1번만 출력해야하므로 출력 후 프로세스를 종료
            printAnswer();
            System.exit(0); // sudoku함수로 돌아가지않고, 프로세스 종료
        }
        // 핵심 로직
        if(arr[row][col]==0){
            for (int k = 1; k <= 9; k++) {
                if(isOK(row,col,k)) {
                    arr[row][col] = k;
                    sudoku(row,col+1);
                }
            }
            //  잘못된 답안으로 답이 나오지 않은 경우, 0으로 초기화 후 백트래킹
            arr[row][col] = 0;
            return;
        }
        sudoku(row,col+1);
    }
    public static boolean isOK(int row,int col,int k){
        // 해당 행에 k 검사
        for(int i=0;i<9;i++)
            if(arr[row][i]==k)
                return false;
        // 해당 열에 k 검사
        for(int i=0;i<9;i++)
            if(arr[i][col]==k)
                return false;
        // 해당 범위에 k 검사
        int n = (row/3)*3;
        int m = (col/3)*3;
        for(int i=n;i<n+3;i++)
            for(int j=m;j<m+3;j++)
                if(arr[i][j]==k)
                    return false;
        return true;
    }
    public static void printAnswer(){
        // 정답 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            sb.append(Arrays.toString(arr[i]).replaceAll("[^0-9 ]", "")).append("\n"); // 공백과 숫자빼고 제거
        }
        System.out.println(sb);
    }
}

✅ 7 14888  연산자 끼워넣기

import java.util.Scanner;
//  18,508kb ,224ms
public class 연산자끼워넣기 {
    static int n;
    static int[] arr;
    static int[] opr = new int[4];
    static int max=Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        // 입력
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        for (int i = 0; i < 4; i++)
             opr[i] = sc.nextInt();
        sc.close();
        // 경우의 수 연산
        dfs(arr[0],1);
        // 정답 출력
        System.out.println(max);
        System.out.println(min);
    }
    public static void dfs(int tmp , int cnt){
        if(cnt == n){
            max = Math.max(max,tmp);
            min = Math.min(min,tmp);
        }
        for (int i = 0; i < 4; i++) {
            if (opr[i] > 0) {
                opr[i] --;
                switch (i) {
                    case 0:
                        dfs(tmp + arr[cnt], cnt + 1);
                        break;
                    case 1:
                        dfs(tmp - arr[cnt], cnt + 1);
                        break;
                    case 2:
                        dfs(tmp * arr[cnt], cnt + 1);
                        break;
                    case 3:
                        dfs(tmp / arr[cnt], cnt + 1);
                        break;
                }
                opr[i]++;
            }
        }
    }

}

✅ 8 14889  스타트와 링크

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

public class Main {
    static int N;
    static int[][] arr;
    static boolean[] flag;
    
    static int ans=Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // input N은 항상 짝수
        arr = new int[N][N];
        flag = new boolean[N];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        bfs(0,0);
        System.out.println(ans);
        br.close();
    }
    public static void bfs(int idx,int choice){
        if(choice == N/2){
            PowerCheck();
            return;
        }
        for (int i = idx; i < N; i++) {
            if (!flag[i]) {
                flag[i] = true;
                bfs(i + 1,choice+1);
                flag[i] = false;
            }
        }
    }
    public static void PowerCheck(){
        int sumA = 0;
        int sumB = 0;
        for (int i = 0; i < N-1; i++) {
             for (int j = i+1; j < N; j++) {
                 if (flag[i]==true && flag[j]==true){
                     sumA += arr[i][j];
                     sumA += arr[j][i];
                 }
                 else if (flag[i]==false && flag[j]==false){
                     sumB += arr[i][j];
                     sumB += arr[j][i];
                 }
             }
        }
        ans = Math.min(ans, Math.abs(sumA -sumB));

        if(ans == 0){ // 최소값이 나왔다면 종료 (효율성을 위해)
            System.out.println(ans);
            System.exit(0);
        }
    }
}