[백준 | Java Bronze I] (#2309) 일곱 난쟁이 - dfs, 완전 탐색 풀이

문제

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

---

접근

 

dfs로 풀었는데, 찾아보니 브루트 포스(완전 탐색) 문제였다. 

dfs로 두 가지 버전으로 풀었는데 둘 다 통과가 되지 않는다 뭐가 문제지? 

--> 06.25 해결 (밑 참고)

 

흥.. 궁시렁궁시렁

첫번째 dfs 코드 - 실패

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

public class Main {
    static int[] dorfs;
    static boolean[] visited;

    public static void dfs(int idx, int depth, int sum, String path) {
        // 일곱 난쟁이를 찾은 경우
        if (depth == 7) {
            // 합이 100이면 출력
            if (sum == 100) {
                String[] s = path.split(" ");
                int[] result = new int[s.length];
                for (int i = 0; i < s.length; i++) {
                    result[i] = Integer.parseInt(s[i]);
                }
                Arrays.sort(result);
                for (int j = 0; j < 7; j++) {
                    System.out.println(result[j]);
                }
            }
            return;
        }

        // 현재 인덱스부터 끝까지 확인
        for (int i = idx; i < 9; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i + 1, depth + 1, sum + dorfs[i], path + dorfs[i] + " ");
                visited[i] = false;
            }
        }
    }

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

        dorfs = new int[9];
        visited = new boolean[9];

        // 난쟁이들의 키 입력 받기
        for (int i = 0; i < 9; i++) {
            dorfs[i] = Integer.parseInt(br.readLine().trim());
        }

        // dfs 호출
        dfs(0, 0, 0, "");

        br.close();
    }
}

 

두번째 dfs 코드 - 실패 

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

public class Main {
    public static int arr[] = new int[9];
    public static int nums[] = new int[7];

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

        for (int i = 0; i < 9; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        dfs(0, 0);
    }

    public static void dfs(int cnt, int start) {
        if (cnt == 7) {
            int sum = 0;
            for (int i = 0; i < 7; i++) {
                sum += nums[i];
            }
            if (sum == 100) {
                Arrays.sort(nums);
                for (int i = 0; i < 7; i++) {
                    System.out.println(nums[i]);

                }
                return;
            }
            return;
        }

        for (int i = start; i < 9; i++) {
            nums[cnt] = arr[i];
            dfs(cnt + 1, i + 1);

        }

    }
}

 

 

🌟 🌟 🌟 🌟 해결!!!!!!!!!!! (2024-06-25)

 

이 문제가 스페셜 저지 문제여서 여러 가지가 정답이 될 수 있을 때, 한 개만. 무조건 출력 했어야 했다. 따라서 출력을 한번 하면 (dfs로 100이 되는 경우를 처음 찾으면) 더 이상 출력되지 않도록 수정해줘야 했다. 

 

해결 된 코드 

package week8.baek;

import java.util.*;
import java.io.*;


public class B2309 {
    static int[] dorfs;
    static boolean[] visited;
    static int flag = 0;

    public static void dfs(int idx, int depth, int sum, String path) {
        // 일곱 난쟁이를 찾은 경우
        if(flag == 0) {
            if (depth == 7) {
                // 합이 100이면 출력
                if (sum == 100) {
                    String[] s = path.split(" ");
                    int[] result = new int[s.length];
                    for (int i = 0; i < s.length; i++) {
                        result[i] = Integer.parseInt(s[i]);
                    }
                    Arrays.sort(result);
                    for (int j = 0; j < 7; j++) {
                        System.out.println(result[j]);
                    }
                    flag = 1;
                }
                return;
            }
        }

        // 현재 인덱스부터 끝까지 확인
        for (int i = idx; i < 9; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i + 1, depth + 1, sum + dorfs[i], path + dorfs[i] + " ");
                visited[i] = false;
            }
        }
    }

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

        dorfs = new int[9];
        visited = new boolean[9];

        // 난쟁이들의 키 입력 받기
        for (int i = 0; i < 9; i++) {
            dorfs[i] = Integer.parseInt(br.readLine().trim());
        }

        // dfs 호출
        dfs(0, 0, 0, "");

        br.close();
    }
}

 

---

최종 코드 - Brute-Force 완전 탐색 이용

package week8.baek;

import java.util.*;
import java.io.*;
public class B2309 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dorfs = new int[9];
        
        //9명의 난쟁이의 합을 구함
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            dorfs[i] = Integer.parseInt(br.readLine());
            sum += dorfs[i];
        }
        
        //완전 탐색 Brute-Force를 사용해서 총합에서 뺄 2명을 선별
        for (int i = 0; i < 8; i++) {
            for (int j = i+1; j < 9; j++) {
                if (sum - dorfs[i] - dorfs[j] == 100) {
                    dorfs[i] = 0;
                    dorfs[j] = 0;
                    Arrays.sort(dorfs);
                    for (int k = 2; k < 9; k++) {
                        System.out.println(dorfs[k]);
                    }
                    return;
                }
            }
        }
    }
}

---

참고

https://propercoding.tistory.com/28

[백준] 2309번 : 일곱 난쟁이 – JAVA [자바]