프로그래머스 : 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버(lv2)

프로그래머스 링크

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

프로그래머스

문제 설명

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 이하인 자연수입니다.

입출력 예numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

DFS풀이 설명 (재귀 방식)

입출력 예 2번을 예로 들어보자

 

numbers 크기가 4이고 4개의 원소와 +, -를 이용하여 4라는 숫자를 만들기 위해서는 2^4번의 계산이 필요하다.

여기서 잘 생각해보면 DFS를 활용하여 풀이할 수 있다는 것이다.

• 재귀가 종료되는 시점을 구해야 됨 (index의 값이 numbers의 크기와 같아질때 종료)
• 처음 재귀는 sum + numbers[index] 원소의 값을 더해주며 판단 (이때 sum + number[index]는 다음 재귀함수의 매개변수로 선언)
• 다음 재귀는 sum - numbers[index] 원소의 값을 빼주며 판단 (이때 sum - number[index]는 다음 재귀함수의 매개변수로 선언)
• 아래 이미지에서 재귀 순서를 본다면 (4,1) - (5, 2) - (7, 3) - (8, 4) - (6, 4) - (3, 3) - (4, 4) - (2, 4) .... 가 되게 됨
• target과 sum의 값이 동일하다면 answer의 값을 증가시켜준다.
• 모든 그래프를 다 돌면 결과적으로 answer의 값을 얻어낼 수 있음

DFS코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;

// DFS
void DFS_Func(vector<int> numbers, int target, int sum, int index)
{
    // index가 number의 크기(size)와 같다면 무한루프를 종료시켜 주어야함.
    if(static_cast<size_t>(index) == numbers.size())
    {
        // sum의값이 target과 같다면 answer를 증가시켜 주어야함
        if(sum == target)
        {
            ++answer;
        }
        
        // 재귀 종료
        return;
    }
    
    // numbers[index]의 값을 더하면서 재귀
    DFS_Func(numbers, target, sum + numbers[index], index + 1);
    
    // numbers[index]의 값을 빼면서 재귀
    DFS_Func(numbers, target, sum - numbers[index], index + 1);
}

int solution(vector<int> numbers, int target)
{
    DFS_Func(numbers, target, 0, 0);
    
    return answer;
}

정확성

BFS풀이 설명

BFS란 너비우선탐색이기 때문에 위에서 설명했던 입출력 예 2번을 예로 다시 설명

그래프 탐색 순서를 보면 (4,1) - (-4, 1) - (5, 2) - (3, 2) - (-3, 2) - (-5, 2)....이(가) 되게 된다.

자세히보면 너비우선이기 때문에 +한번 - 한번 순차적으로 진행하여 그래프 가로줄을 순서대로 탐색하는것을 알 수 있다.

BFS코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

queue<pair<int, int>> q;
int solution(vector<int> numbers, int target)
{
    int answer = 0;
    int Size = numbers.size();
    // 첫 숫자 push하는데 BFS이기 때문에 + - 값을 동시에 넣어준다.
    q.push({ numbers[0], 1 });
    q.push({ -numbers[0], 1 });
    // 두번째 숫자부터 큐가 비어있지 않다면 반복
    while (!q.empty()) 
    {
        int Sum = q.front().first;
        int Index = q.front().second;
        q.pop();
        // 타겟이랑 Sum이랑 같으면 answer증가
        if (Index == Size)
        {
            if (Sum == target) 
            {
                answer++;
            }
        }
        // 끝이 아닌 경우에는 현재 숫자와 numbers의 숫자의 합, 차를 push
        else 
        {
            q.push({ Sum + numbers[Index], Index + 1 });
            q.push({ Sum - numbers[Index], Index + 1 });
        }
    }
    return answer;
}

BFS 풀이 정확성