[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 타켓넘버(43165)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

public class Solution {

	public static void main(String[] args) {
		int[] numbers = { 1, 1, 1, 1, 1 };
		int target = 3;
		// which returns 5
		System.out.println(solution(numbers, target));
	}

	static int pos = 0;
	static int count = 0;

	static int solution(int[] numbers, int target) {
		int answer = 0;
		
		search(numbers, target);
		answer = count;

		return answer;
	}

	static void search(int[] numbers, int target) {
		if (pos == numbers.length && target == 0) { count++; return; }
		if (pos == numbers.length)	return;

		target = target - numbers[pos++];
		search(numbers, target);
		target = target + numbers[--pos];

		target = target + numbers[pos++];
		search(numbers, target);
		target = target - numbers[--pos];
	}

}

 

 루트 0에서 배열의 숫자 순서대로 더하는 경우(양의 경우)와 빼는 경우(음의 경우)로 나뉘는 트리 구조를 떠올리고, 재귀적인 방법으로 이를 순회하는, 그래프의 탐색 알고리즘을 사용하였다. 정점을 방문하는 순서는 깊이 우선 탐색과 유사하지만 트리 구조로 두 갈래로만 나뉘기 때문에 방문 여부는 체크는 하지 않고, 양의 경우를 처리한 후에 재귀하여 음의 경우를 처리한다.