[백엔드TIL] DFS 개념 및 부분집합 문제

DFS

 

· DFS(Depth-First Search)는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 

알고리즘 동작 방식

· 스택 자료구조를 이용한다.

 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.

 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고,

     방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

* ‘방문 처리': 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 이를 통해 각 노드를 한 번씩만 처리할 수 있다.

 

 

부분집합 문제

 

설명

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.Scanner;

public class Main {

public static String answer = "NO";

public static int n = 0;
public static int total = 0;

public static boolean flag = false;

public void DFS (int l , int sum, int[] nums) {
if (flag) return;
if (sum > total / 2) return;
if (l == n) {
if ((total - sum) == sum) {
answer = "YES";
flag = true;
}
} else {
DFS(l+1, sum+nums[l], nums);
DFS(l+1, sum, nums);
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Main T = new Main();
n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
total += nums[i];
}
T.DFS(0, 0, nums);
System.out.println(answer);
}
}

예시 입력) 

6
1 3 5 6 7 10  

 

해설 ) 

 배열 값과 총합(total)을 구한다 

 

DFS 함수에 매개변수로 초기값 전달 

 

total 과 배열값은 공유변수로 관리 

 

루트에서 

1, 1, 배열

1, 0, 배열 

두가지 재귀함수 실행 

 

부분배열의 합이 절반값 ex 16 일때까지 함수 반복 

 

중간에 flag 값이 true 거나 sum이 전체합 나누기 2보다 클때는 해당 메소드 종료 

flag값이 true 라면 이후의 모든 함수 종료 

 

총합 /2 인값이 있다면 서로소인 부분집합이 있다는 뜻