[BOJ - JAVA] 3040 - 백설 공주와 일곱 난쟁이(브루트포스, 백트래킹)

# 주소

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

3040번: 백설 공주와 일곱 난쟁이

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    static int[] arr,ans;
    static int sum;
    static boolean[] visit;
    static StringBuilder sb;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        arr = new int[9];
        visit = new boolean[9];
        for(int i = 0; i < 9; i++){
            arr[i] = scan.nextInt();
        }
        ans = new int[7];
        bfs(0, 0);
        System.out.println(sb);
    }
    public static void bfs(int index, int sum){
        if(index == 7){
            if(sum == 100){
                sb = new StringBuilder();
                for(int val : ans) {
                	sb.append(val).append('\n');
                }
            }
            return;
        }
        for(int i = index; i < 9; i++){
            if(!visit[i]){
                visit[i] = true;
                ans[index] = arr[i];
                bfs(index+1, sum + arr[i]);
                visit[i] = false;
            }
        }
    }
}

브루트포스 문제인데 백트래킹으로 풀었습니다.

입력되는 인덱스가 9이고 최종적으로 합이 100이 되는 인덱스 7의 값을 찾아내면 되기 때문입니다.

따라서 방문한 인덱스와 방문하지 않은 인덱스를 구분하기 위해 boolean 타입의 visit을 선언합니다.

 

그리고 크기가 9인 arr와 그 arr 중 7개의 값을 넣을 ans를 선언합니다.

bfs함수로 들어가 인자는 2개를 선언합니다. 하나는 index가 7이 될 때 출력해야 하므로 int타입의 index와 합이 100이 될 떄 출력할 int타입의 sum을 인자로 가져옵니다.

StringBuilder를 사용해서 풀이를 할 것이므로 sb를 생성합니다.

제일 밑의 for문으로 내려가서 visit[i]가 false일 떄(방문하지 않은 값) ans[index]에 arr[i]를 담습니다.

그리고 bfs(index + 1, sum + arr[i])를 실행하는데, index를 +1, sum에 arr를 더하여 ans에 담겠단 뜻입니다.

 

다시 위의 if(index == 7)고 sum == 100일 때 ans를 sb에 담아서 최종적으로 출력하면 되겠습니다.

감사합니다.