[BOJ] 21단계 백트래킹

백트래킹: 모든 경우를 탐색

 

1

15649

N과 M (1)

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

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

public class Main {

    private static int N, M;
    private static int[] arr;
    private static boolean[] visit;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        arr = new int[M];
        visit = new boolean[N];
        dfs(0);
        System.out.print(sb);
    }

    public static void dfs(int depth) {
        if(depth == M) {
            for(int val : arr) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }
        for(int i = 0; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                arr[depth] = i + 1;
                dfs(depth + 1);
                visit[i] = false;
            }
        }
    }
}

*깊이 우선 탐색 DFS

 

2

15650

N과 M (2)

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

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

public class Main {

    private static int N, M;
    private static int[] arr;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        arr = new int[M];
        dfs(0, 0);
        System.out.print(sb);
    }

    public static void dfs(int depth, int start) {
        if(depth == M) {
            for(int val : arr) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }

        //이전 깊이 원소의 다음 숫자부터 탐색하기 때문에 방문 여부 체크가 필요 없다.
        for(int i = start; i < N; i++) {
            arr[depth] = i + 1;
            dfs(depth + 1, i + 1);
        }
    }
}

 

3

15651

N과 M (3)

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

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

public class Main {

    private static int N, M;
    private static int[] arr;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        arr = new int[M];
        dfs(0);
        System.out.print(sb);
    }

    public static void dfs(int depth) {
        if(depth == M) {
            for(int val : arr) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < N; i++) {
            arr[depth] = i + 1;
            dfs(depth + 1);
        }
    }
}

 

4

15652

N과 M (4)

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

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

public class Main {

    private static int N, M;
    private static int[] arr;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);

        arr = new int[M];
        dfs(0, 0);
        System.out.print(sb);
    }

    public static void dfs(int depth, int start) {
        if(depth == M) {
            for(int val : arr) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = start; i < N; i++) {
            arr[depth] = i + 1;
            dfs(depth + 1, i);
        }
    }
}

 

5

9663

N-Queen

 

7

14888

연산자 끼워넣기

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

public class Main {
    private static final int[] operator = new int[4];
    private static int[] operand;
    private static int N;
    private static int min = Integer.MAX_VALUE;
    private static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        operand = new int[N];
        for(int i = 0; i < N; i++) {
            operand[i] = Integer.parseInt(tokenizer.nextToken());
        }
        tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < 4; i++) {
            operator[i] = Integer.parseInt(tokenizer.nextToken());
        }
        operation(operand[0], 1);
        System.out.println(max + "\n" + min);
    }

    public static void operation(int result, int idx) {
        if(idx == N) {
            if(result < min) {
                min = result;
            }
            if(result > max) {
                max = result;
            }
            return;
        }
        for(int i = 0; i < 4; i++) {
            if(operator[i] > 0) {
                operator[i]--;
                switch (i) {
                    case 0:
                        operation(result + operand[idx], idx + 1);
                        break;
                    case 1:
                        operation(result - operand[idx], idx + 1);
                        break;
                    case 2:
                        operation(result * operand[idx], idx + 1);
                        break;
                    case 3:
                        operation(result / operand[idx], idx + 1);
                        break;
                }
                operator[i]++;
            }
        }
    }
}

 

8

14889

스타트와 링크

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

public class Main {
    private static int N;
    private static int[][] S;
    private static boolean[] team;
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());
        team = new boolean[N];
        S = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for(int j = 0; j < N; j++) {
                S[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    public static void dfs(int depth, int start) {
        //start 팀원(N/2명) 선택이 끝나면 나머지 인원은 자동으로 link 팀이 됨
        if(depth == N/2) {
            int teamStart = 0;
            int teamLink = 0;
            for(int i = 0; i < N - 1; i++) {
                for(int j = i + 1; j < N; j++) {
                    if(team[i] && team[j]) {
                        teamStart += S[i][j];
                        teamStart += S[j][i];
                    } else if(!team[i] && !team[j]) {
                        teamLink += S[i][j];
                        teamLink += S[j][i];
                    }
                }
            }

            int gap = Math.abs(teamStart - teamLink);
            if(gap == 0) {
                System.out.println(gap);
                System.exit(0);
            } 
            min = Math.min(min, gap);
            return;
        }
        for(int i = start; i < N; i++) {
            if(!team[i]) {
                team[i] = true;
                dfs(depth + 1, i + 1);
                team[i] = false;
            }
        }
    }
}