프로그래머스 > 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 이하인 자연수입니다.

입출력 예

생각하기

말이 네트워크지 쉽게 이해하자면 그냥 간선으로 이동할 수 있는 노드들은 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]);  
    }
}