[프로그래머스] 타겟 넘버 - LEVEL2

🔗 문제 링크

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

✍️ 문제 풀이

이 문제는 DFS 방식으로 풀었다. 처음에는 단순히 for문이 먼저 생각 났는데, for문으로 풀 경우 numbers의 수가 하나 늘어날 때마다 for문이 하나 더 중첩된다. numbers의 수가 적을 경우에는 가능하겠지만 최대 20개이기 때문에 비효율적일 것이다.

해당 문제는 numbers의 각 수들을 더하느냐, 빼느냐 두 가지의 선택지가 존재한다.
따라서 모든 경우의 수를 생각하면 2의 (numbers의 개수)승 만큼의 경로가 있게 된다.

모든 경로를 끝까지 탐색하지 않고 결과값이 target인 경로만 찾을 수 있다면 좋겠지만, 이는 불가능하므로 DFS 방식을 사용해 최하단 노드까지 가는 모든 경로를 찾고자 한다.

문제에 있는 예시 중 numbers가 [4, 1, 2, 1]이고, target이 4인 경우를 구현해보겠다.

1) 4와 -4는 연결되어있지 않아 4 또는 -4에서 시작할 경우 반대편 그래프에 대한 경로를 찾을 수 없기 때문에 최상단에 0이라는 노드를 하나 추가해 모든 노드가 이어지게 할 것이다.

2) DFS 함수 내부에서는 depth를 체크하여 최하단 노드가 아닐 경우에는 currentSum에 다음 노드에 해당하는 숫자를 누적하고 DFS 함수를 재귀 호출한다. 최하단 노드가 아닐 경우 각 노드에는 절대값이 같은 두 노드가 인접해 있으므로 재귀 호출 또한 두 번 해준다.

3) 만약 최하단 노드에 도착했다면 지금까지의 currentSum 누적 값을 확인해 target과 같다면 전역 변수인 count의 값을 1 증가시켜준다.

4) 이후 모든 경로를 탐색해 DFS 함수가 종료되면 solution에서 count값을 return하게 된다.

* 코드 중간에 보면 answer라는 변수가 있는데, 이는 처음에 문제를 잘못 읽어서 경로도 출력해야하는 줄 알고 경로를 누적시킨 변수이다 ㅎㅎ.. 이왕 구했는데 지우기는 아까워서 적음...

재귀 함수의 실행 순서가 헷갈릴 수도 있어서 일정 부분까지만 순서를 살펴보겠다.

DFS(depth = 0, currentSum = 0)
	DFS(depth = 1, currentSum = 4)
    	DFS(depth = 2, currentSum = 5)
        	DFS(depth = 3, currentSum = 7)
            	DFS(depth = 4, currentSum = 8)
                DFS(depth = 4, currentSum = 6)
            DFS(depth = 3, currentSum = 3)
            	DFS(depth = 4, currentSum = 4)
                DFS(depth = 4, currentSum = 2)
        DFS(depth = 2, currentSum = 3)
        ... 

이와 같은 순서로 실행된다.

🖥️ 풀이 코드

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int depth = 0;
string stack = "";
int count = 0;

void DFS(int, int, vector<int>, string, int);

int solution(vector<int> numbers, int target) 
{
	numbers.insert(numbers.begin(), 0);
    DFS(depth, target, numbers, stack, 0);
	return count;
}

void DFS(int depth, int target, vector<int> numbers, string stack, int sum)
{
	string answer = stack;
	int currentSum = sum;
	
	if(depth < numbers.size() - 1)
	{
		currentSum += numbers[depth + 1];
		answer += "+" + to_string(numbers[depth + 1]);
		DFS(depth + 1, target, numbers, answer, currentSum);
		
		currentSum -= numbers[depth + 1] * 2;
		answer = stack;
		answer += to_string(numbers[depth + 1] * -1);
		DFS(depth + 1, target, numbers, answer, currentSum);
	}
	else if(currentSum == target)
	{
		//cout << answer + " = " + to_string(currentSum) << endl;
		count++;
	}
}