프로그래머스 [깊이/너비 우선 탐색(DFS/BFS)] 타겟 넘버(C++) -yes6686- 티스토리

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

---

문제 링크: 문제 보기

문제 설명:

주어진 숫자 리스트에서 각 숫자를 더하거나 빼서 목표 숫자를 만들 수 있는 경우의 수를 구하는 문제입니다. 깊이 우선 탐색(DFS)을 활용하여 모든 경우를 탐색하고 조건을 만족하는 경우를 카운트합니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int arr[21]; // 숫자 배열 저장
int ans = 0; // 정답 카운트

// DFS를 이용한 탐색
void dfs(int depth, int sum, int target, int size) {
    if (depth == size) { // 모든 숫자를 탐색했을 때
        if (sum == target) { // 목표값과 동일하면 카운트 증가
            ans++;
        }
        return;
    }
    // 현재 숫자를 더하는 경우와 빼는 경우 모두 탐색
    dfs(depth + 1, sum + arr[depth], target, size);
    dfs(depth + 1, sum - arr[depth], target, size);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    // 배열 복사
    for (int i = 0; i < numbers.size(); i++) {
        arr[i] = numbers[i];
    }

    // DFS 탐색 시작
    dfs(0, 0, target, numbers.size());

    answer = ans;
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 모든 숫자에 대해 더하기와 빼기 두 가지 선택지를 고려하여 DFS를 수행합니다. 목표값과 일치하는 경우를 카운트합니다.
• 구현 세부사항:
• dfs 함수는 현재 위치에서 숫자를 더하거나 빼며 탐색을 진행합니다.
• 모든 숫자를 사용했을 때(depth == size) 목표값과 비교하여 카운트를 증가시킵니다.
• 배열을 전역 변수 arr에 복사하여 함수 호출 시 인자 전달을 최소화하였습니다.
• 시간 복잡도 분석:
• DFS의 탐색 깊이는 최대 n이며, 각 숫자에 대해 두 가지 선택(더하기, 빼기)이 가능합니다.
• 따라서, 최악의 경우 시간 복잡도는 O(2^n)입니다.

---

결과

이 코드는 주어진 숫자로 목표값을 만들 수 있는 모든 경우의 수를 정확히 탐색하여 반환합니다. DFS를 활용하여 모든 경우를 탐색하는 기본적인 문제 풀이 방식입니다.

다른 접근 방식으로는 동적 계획법(DP)이나 BFS(너비 우선 탐색)을 활용하여 탐색 공간을 줄이는 방법도 고려할 수 있습니다. 특히 입력 크기가 크다면 BFS를 사용하여 메모리 사용을 줄이는 것이 효과적일 수 있습니다.