프로그래머스 - 타겟 넘버 (DFS, BFS) Python

문제 설명

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

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

입출력 예 설명

문제에 나온 예와 같습니다.

---

• numbers의 숫자들을 더할 경우, 뺼 경우, 이 두 경우를 가지로 해서 트리를 만들 수 있다.

BFS를 이용한 풀이

• numbers의 숫자를 더하거나 뺀 경우를 수평적으로 추가해준다.
• 결국 leaves리스트에 모든 계산 결과가 담기게 된다. 이후 target값과 비교해서 결과 출력.

#BFS 풀이
def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

DFS를 이용한 풀이

• BFS가 수평적으로 더해 한꺼번에 모든 결과값을 얻었다면, DFS를 이용할 땐 하나씩 비교한다
• depth 변수 값을 통해 탐색 중인 트리의 깊이를 알 수 있다.
• 트리 끝에 도착했다면, number값을 모두 더한 값을 비교한다.

#DFS 풀이
def solution(numbers, target):
    answer = DFS(numbers, target, 0)
    return answer

def DFS(numbers, target, depth):
    answer = 0
    if depth == len(numbers):
        print(numbers)
        if sum(numbers) == target:
            return 1
        else: return 0
    else:
        answer += DFS(numbers, target, depth+1)
        numbers[depth] *= -1
        answer += DFS(numbers, target, depth+1)
        return answer

---

feedback

1. 이 문제는 스스로 해결하지 못하고 구글의 도움을 받아 해결했다. 풀이를 찾아보기 전, 해답의 아이디어를 스스로 생각해 냈지만 실행에 옮기지 않고 포기했다.
2. 모든 수는 더하기, 빼기, 이 두가지 경우의 수 만 존재하므로, 해답처럼 모두 결과를 계산하고 찾는 아이디어를 떠올렸다. 하지만 모든 경우를 계산하므로 시간복잡도가 2^n였고, 이런게 해답일리 없다고 생각했다.
3. 하지만 실제 풀이는 해당 아이디어와 비슷했다. 역시 머릿속에서 생각하는 것 보단 어떤 코드라도 일단 작성해봐야 한다.
4. DFS를 구현하는 데 생각보다 오랜 시간이 걸렸다. 다른 풀이에서 사용된 global 을 빼고 작성하고 싶었다. 이 때 스스로 코드를 재귀적으로 작성하는 것에 익숙하지 않다보니 머릿속에서 정리가 되지 않았다.