[파이썬/Python/프로그래머스] DFS/BFS > 타겟 넘버

프로그래머스 코딩테스트 연습 > DFS/BFS > 타겟 넘버를 풀었다.

DFS/BFS 문제에 익숙하지 않아 고민 하다가 다른 사람의 코드를 참고 해서 풀었다.

• dfs 함수를 만들어서 인덱스(i)와 n이 같은 경우, 그리고 합(s)가 target과 같게되면 answer을 1 증가시킨다.
• 합(s)와 target이 같지 않으면 함수를 넘어간다.
• 만약 인덱스(i)와 n이 같지 않으면 else문으로 넘어가 +와 -에 대한 dfs 함수를 실행한다.
• 여기서 +와 -에 대한 dfs함수를 실행하는 것은 트리를 그릴 때 가지치기 하는 것과 같다.

def solution(numbers, target):
    n=len(numbers)
    answer = 0
    def dfs(i,s):
        if i==n:
            if s == target:
                nonlocal answer
                answer+=1
        else:
            dfs(i+1,s+numbers[i])
            dfs(i+1,s-numbers[i])
    dfs(0,0)
    return answer

참고한 코드 : https://velog.io/@ju_h2/Python-프로그래머스-level2-타겟넘버-BFSDFS