[JAVA] DFS/BFS "타겟 넘버"

"가지치기 하면서 더해야된다???"

→ return (재귀메소드  + 재귀메소드)

2의 제곱수마다 i값을 증가시켜가며 add를 지속해나가면서 노드에 더하거나 뺀다.

"가지치기 하면서 더해야된다???"

"q.add(첫번째방식);  q.add(두번째방식);"

 

 

DFS/BFS 문제를 처음 접해서 다른 이들의 코드를 참고했다.

 

다음은 DFS 코드이다..예술이다..

class Solution {
​​​​public int solution(int[] numbers, int target) {
​​​​​​​​int answer = 0;
​​​​​​​​answer = dfs(numbers, 0, 0, target);
​​​​​​​​return answer;
​​​​}
​​​​int dfs(int[] numbers, int n, int sum, int target) {
​​​​​​​​if(n == numbers.length) {//노드를 모두 탐색했을때만 타겟과 합이 같은지 검사한다
​​​​​​​​​​​​if(sum == target) {
​​​​​​​​​​​​​​​​return 1;
​​​​​​​​​​​​}
​​​​​​​​​​​​return 0;
​​​​​​​​}
​​​​​​​​return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
​​​​}
}

 

위처럼, return할때 아래와 같은 방식으로 dfs를 끝까지 실행한다.

1. numbers[n]을 더하는 경우

2. numbers[n]을 빼는 경우

이렇게 점점 가지치기해나가면서 카운트해서 최종적으로 answer로 리턴된다.

 

"가지치기 하면서 더해야된다???"

→ return (재귀메소드  + 재귀메소드)

 

아직까지는 DFS/BFS의 개념을 정확히 체감하지 못했다.

하지만 느낀바로는, DFS/BFS인지를 인지하는 것보다 어떤 방식으로 코드를 짤 것인지만 알게된다면 굳이 구별할 필요는 없다고 생각한다.

 

다음은 BFS방식으로 푼 풀이에 대해 알아보겠다.

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
​​​​public int solution(int[] numbers, int target) {
​​​​​​​​int answer = 0;
​​​​​​​​answer=bfs(numbers[0],numbers,target);
​​​​​​​​System.out.println(answer);
​​​​​​​​return answer;
​​​​}
​​​​public static int bfs(int start,int[] v,int target) {
​​​​​​​​Queue<Integer> q= new LinkedList<>();
​​​​​​​​q.add(start);
​​​​​​​​q.add(-start);
​​​​​​​​int i=0,k=0,kk=2;

​​​​​​​​while(q.size()!=Math.pow(2, v.length)) {
​​​​​​​​​​​​int temp=q.poll();
​​​​​​​​​​​​if(k==kk) {
​​​​​​​​​​​​​​​​i++;kk+=Math.pow(2, i+1);//왜 2의제곱으로 경우의 수가 가지치기로 늘어나기 때문에,
​​​​​​​​​​​​​​​​// i를 2의제곱수가 될때마다만, 증가해줘야함.
​​​​​​​​​​​​​​​​
​​​​​​​​​​​​​​​​//System.out.println("???"+i);
​​​​​​​​​​​​}
​​​​​​​​​​​​//System.out.print(temp+" ");
​​​​​​​​​​​​q.add(temp+v[i+1]);
​​​​​​​​​​​​q.add(temp-v[i+1]);
​​​​​​​​​​​​k++;
​​​​​​​​}

​​​​​​​​int cnt=0;
​​​​​​​​//System.out.println();
​​​​​​​​while(!q.isEmpty()){
​​​​​​​​​​​​int temp=q.poll();

​​​​​​​​​​​​//System.out.print(temp+"!");
​​​​​​​​​​​​if(temp==target)cnt++;
​​​​​​​​}
​​​​​​​​return cnt;
​​​​}
}

첫번째 while문이 bfs의 방식이다.

큐에다가 가지치기로 add를 해주면서 2의 제곱수마다 i값을 증가시켜가며 add를 지속해나가면서 노드에 더하거나 뺀다.

 

이런식으로 사고의 흐름대로 구현이 가능하다.

"가지치기 하면서 더해야된다???"

"q.add(첫번째방식);  q.add(두번째방식);"

 

결론적으로,

DFS -> return 재귀메소드+재귀메소드

BFS -> q.add(a+i); q.add(a-i); 

 

위와 같은 방식으로 생각해내면 가지치기가 된다.