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

 

 

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); 

 

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