[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) 타겟넘버 _ 자바Java

난이도: Level 2

 1. 문제  

| 문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

| 제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

 

| 입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

---

 2. 알고리즘 by Yoon 

 

이 문제는 DFS의 가장 대표적인 문제라 할 수 있는데, 우선 위 그림을 예시로 들어 알고리즘을 설명하도록 하겠다.

• input 값으로 들어오는 numbers의 배열 길이만큼 level의 높아진다.
• 시작점(start)을 기준으로 +일 수도 있고, -일 수도 있기 때문에 두 갈래 left와 right로 나뉘어 DFS가 적용된다.
• 재귀(recursion) 함수가 사용된다. 

1. 우선 dfs라는 함수를 호출할 때 인자 값으로는 numbers의 배열, target, 그리고 추가적으로 level 값(level)과 해당 레벨까지의 원소 합(sum)이 필요하다. 따라서, 처음에는 level이 0이고 sum도 0이므로 dfs(numbers, target, 0, 0)으로 시작한다.

2. 경우의 수는 +와 -이므로 level을 증가시키는 동시에 (지금까지 누적된 sum + level까지의 원소 합인 numbers[level])를 인자로 수정하여 dfs를 다시 호출한다.

3. recursion을 종료시키는 조건문으로는 level이 numbers 배열의 길이와 동일해 졌을 때 모든 원소의 경우의 수를 다 보았다는 뜻이므로 해당 조건문에 따라 값을 return 해준다. 

          3.1 이때 sum이 목표로 하는 target 값과 일치하면 1을 return 한다.

          3.2 그렇지 않으면 0을 return 한다.

4. 그렇게 조건에 맞는 target과 sum이 동일한 경우에만 return 했던 1의 값이 누적되면서 answer가 증가한다.

 

최종적으로는 문제에서 주어진 예제에 대해 아래와 같이 그릴 수 있고,  빨간 동그라미가 답이 된다!

 

---

 3. 소스코드 

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    public int dfs(int[] numbers, int target, int level, int sum){
        
        // 배열 길이만큼 level이 증가하고, 각 원소들의 합이 target과 동일한 경우 
        if(level == numbers.length){
            if(target == sum) return 1;
            else return 0; 
        }
		// left						   // right
        return dfs(numbers, target, level+1, sum + numbers[level])+ dfs(numbers, target, level+1, sum - numbers[level]);
        
    }
}

 

 

---

 4. 느낀점 

문제를 읽자마자 DFS라는 것은 한 번에 파악 되었고, DFS의 대표적인 문제라고 생각했다.recursion이기 때문에 바로바로 떠오르지는 않았지만, dfs함수를 호출할 때마다 달라져야 하는 값과 recursion을 끝내야 하는 조건들을 생각해보니 금방 해결할 수 있었다. 그리고 무엇보다 소름이었던 건 내가 짠 코드가 프로그래머스 '다른 사람의 풀이'에서 인기 순위가 높은 코드와 동일했다. 조금 많이 뿌듯했다!!! @'-'@

 

 

 

 

[Algo Rhythm🕺💃]

날짜: 2020.07.08