[ 프로그래머스 - 타켓 넘버 ] DFS

 

• 이 문제와 dfs의 연관 관계?
• dfs는 재귀와 관련있는데, 재귀를 이 문제에 어떻게 적용?
• dfs의 흔한 예로 '경로 찾기'가 있는데 '경로 찾기'를 이 문제에 어떻게 변형, 적용?

 

풀이

def dfs(nums, i, n, t):
    ret = 0
    if i==len(nums):
        if n==t: return 1
        else: return 0
    ret += dfs(nums, i+1, n+nums[i], t)
    ret += dfs(nums, i+1, n-nums[i], t)
    return ret

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

• ret를 dfs안에 선언해도 되는 이유

ret는 dfs의 첫 줄에 0으로 선언되면서 초기화된다. 우리는 ret의 누적값을 구해야 하는데, 

'누적'이 되게 하기 위해 재귀에 들어가는 부분에서 ret  += dfs(nums, i+1, n+nums[i], t) 라고 써주었다.

 

 

이 코드를 완벽히 이해하지 못했다 ... 다음에 모각코할때 물어봐야겠다

 

+확실히 아직까지 수학적 논리를 코드로 옮기는 능력이 부족한 것 같다. 이 훈련을 꾸준히 해야겠다

++재귀, dfs, bfs 문제들을 더 많이 풀어봐야 겠다