깊이/너비 우선 탐색(DFS/BFS) Level 2 타겟 넘버 - python (프로그래머스)

소스 코드

def dfs(index, sum, target, numbers):
    
    if index == len(numbers):
        if sum == target:
            return 1
        else:
            return 0
    return dfs(index+1, sum + numbers[index], target, numbers) + dfs(index+1, sum - numbers[index], target, numbers)

def solution(numbers, target):
    
    
    answer = 0
    answer = dfs(0, 0, target, numbers)
    
    return answer

print(solution([1,1,1,1,1], 3))

풀이

위 문제는 백준에서도 본적 있는거 같아서 쉽게 풀었던거 같다.

나올수 있는 정수의 형태는 더하거나 뺴기 두 가지 경우 밖에 없으므로 두 경우에 대한 과정을 dfs로 표현하면 됐다. 따라서 dfs 함수 내에서 해당 숫자를 더한 경우에 대한 함수 호출과 숫자를 뺀 경우에 대한 호출을 해준다.

 

탈출 조건으로는 target 넘버를 찾았을 경우 이거나 아니면 target 넘버가 아닌 경우 다시 돌아가기 위한 조건이다.