프로그래머스 > DFS/BFS > 타겟넘버
https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

---

문제

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
[4, 1, 2, 1]	4	2

---

생각하기

말이 네트워크지 쉽게 이해하자면 그냥 간선으로 이동할 수 있는 노드들은 1로 계산하고 따로 떨어져있는 노드들도 1로 계산해서 모두 더하면 되는 문제였다.

computers[][] 배열이 2차원 배열이지만 사실 자기자신을 경계로 봤을 때,
아랫면이든 윗면이든 한쪽만 보면된다.
그래서 visit[] 배열을 computers.length의 길이 만큼 1차원 배열로 생성해주면 된다.

DFS

재귀를 이용하여 구현을 해봤다.

+와 -의 조합으로 이루어지기 때문에 2개의 조합으로만 구성된다.

index는 어차피 숫자가 계속 누적되면서 쌓이고 부호만 바뀌기 때문에
index는 + 1은 변하지 않는다.

다음은 sum에서 +와 - 기호를 구분하기 위해
sum + numbers[index]
sum - numbers[index] 로 2가지로만 구분하면된다.

이렇게 되면 재귀를 하면서 각 숫자에 대한 + - 조합을 모두 해보면서
target과 같은 숫자일 경우 answer이 증가하여
원하는 값을 출력할 수 있다.

탈출 조건은 numbers 배열을 넘어가면 안되기 때문에 index값을 numbers배열의 길이와 같아질 경우 return 시키도록 설정해주었다.

TMI

복잡하지 않는 내용인데 2번째 부터 돌아가는 재귀는 항상 머리가 복잡해진다.
손으로 직접쓰는게 최고!

---

코드

DFS 사용

class Solution {
	static int numbers[];
	static int target;
	static int answer = 0;
	static int length;

    public int solution(int[] numbers, int target) {
    	this.numbers = numbers;
    	this.target = target;
    	this.length = numbers.length;

    	DFS(0, 0);

        return answer;
    }

    static void DFS(int index, int sum) {
    	// 탈출 조건
    	if(index == length) {
    		if(sum == target) answer++; 
    		return;
    	}

    	// 수행 동작
    	DFS(index + 1, sum + numbers[index]);
    	DFS(index + 1, sum - numbers[index]);  
    }
}