[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS - 기출문제
DFS, BFS 기출문제 풀이
합이 같은 부분집합(DFS : 아마존 인터뷰)
-
설명 : N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES”를 출력하고, 그렇지 않으면 ”NO”를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
-
입력 : 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.
-
출력 : 첫 번째 줄에 “YES” 또는 ”NO”를 출력한다.
-
풀이 답안
import java.util.*;
public class Main {
static double total = 0;
static int num;
static String result = "NO";
static int[] arr;
public void DFS(int v, int sum){
if(v>num) return;
if(v==num) {
if(total/2==sum) result="YES";
} else {
DFS(v+1, sum+arr[v+1]);
DFS(v+1, sum);
}
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
num = scan.nextInt();
arr = new int[num+1];
for(int i=1; i<=num; i++){
int a = scan.nextInt();
arr[i] = a;
total += a;
}
main.DFS(0, 0);
System.out.println(result);
}
}
- 정리
- 우선 값과 데이터를 담을 배열을 만들어 arr배열 안에 입력된 원소들을 담았다.
- 그리고 데이터를 받을때 바로 total 합계도 더해주었다
- DFS 진입 (이때 DFS에 반영되는 매개변수는 직접적인 데이터가 아니라 순번과 합계를 넣어주도록 했다. 초기값은 0번, 합계 0)
- v가 최종 순번 (num)을 초과하면 return
- v가 최종 순번과 일치하면 총합이 total/2와 같은지 비교해서 같다면 result를 YES로 변경 (두개의 부분집합이 같아야 하는것이기 때문에 각각의 부분집합이 total의 절반이 되어야만 함)
- 아직 최종순번에 다다르지 않았다면 DFS를 두번 도는데(트리구조) 이때 sum을 더하는경우와 더하지않는경우를 만들어 줌
- 중요한것은 totla을 int가 아닌 double로 선언하여 홀수일때를 걸러줘야함
- 우선 값과 데이터를 담을 배열을 만들어 arr배열 안에 입력된 원소들을 담았다.
- 개선 답안
import java.util.*;
public class Main {
static double total = 0;
static int num;
boolean flag = false;
static String result = "NO";
static int[] arr;
public void DFS(int v, int sum){
if(flag) return;
if(sum>total/2) return;
if(v==num) {
if(total/2==sum) {
result="YES";
flag=true;
}
} else {
DFS(v+1, sum+arr[v+1]);
DFS(v+1, sum);
}
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
num = scan.nextInt();
arr = new int[num+1];
for(int i=1; i<=num; i++){
arr[i] = scan.nextInt();
total += arr[i];
}
main.DFS(0, 0);
System.out.println(result);
}
}
- 정리
- 전체적인 풀이 방식은 동일하나 두가지 개선점이 있음
- boolean타입의 변수를 하나 선언해두어 “YES”로 변경되었다면 하위노드들은 체크하지않고 모두 return처리 해도 됨
- if(v>num) return;으로 종료처리 하는것도 기능상 맞긴하지만 이미 절반의수가 넘의 경우에도 계속 돌게됨, if(sum>total/2) return;로 해주면 매개변수가 과반수이상 커진경우 리턴됨
- 전체적인 풀이 방식은 동일하나 두가지 개선점이 있음