[프로그래머스/파이썬] 타겟 넘버 풀이 (Python, dfs, 재귀함수)

[프로그래머스/파이썬] 타겟 넘버 풀이 

(Python, dfs, 재귀함수)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

---

2. 문제 해결 아이디어 (풀이)

 

* DFS를 실행할 때, 계산의 마지막을 판단하는 방법은 'depth'이다.

 

1. number 배열의 숫자를 차례대로 계산한다. (depth로 숫자 index 판단)

1.1. 이때 각 숫자마다 (+,-)를 한번씩 대입해서 계산한다.

- (참고로, 처음부터 -가 붙을 수 있으니, 0에서 값을 더하거나 빼는 방식으로 진행)

 

2. 끝까지 1번 로직을 반복하면서, 최대 깊이에 도달하면 (numbers 길이만큼), 계산된 값을 비교하고, dfs를 종료한다.

2.1. 현재까지 계산된 수가 target과 일치하다면 개수를 +1 해준다.

 

---

3. 코드

count = 0

# 타겟 넘어를 찾는 수
def dfs(depth, num, numbers, target):
    global count # 개수 저장 
    
    # 마지막 계산까지 했다면 종료. (depth로 마지막까지 도착했는지) 
    # (numbers 길이는 4, 인덱스는 0부터 시작하기 때문에 len에 다다르면 끝남 )
    if depth == len(numbers):
        #마지막 계산인데 목표값과 일치하다면?
        if num == target:
            count+=1
        return 
    
    # dfs로, 현재 계산을 끝까지 진행 (+,- 각각 진행)
    dfs(depth+1, num+numbers[depth], numbers, target)
    dfs(depth+1, num-numbers[depth], numbers, target)
    

    return 

def solution(numbers, target):
    answer = 0
    depth = 0 # dfs 깊이, 즉 현재 계산할 numbers의 번호, 인덱스 
    num = 0 # dfs에서 계산하고 있는 값
    
    dfs(depth, num, numbers, target)
    answer = count
 
    return answer

- 참고로, 찾은 개수를 저장하는 'count' 변수는 '전역 변수'로 만들어줬다.

- 함수 안에서 전역 변수를 사용하려면 'global' 키워드를 사용하면 된다. 

 

(global 키워드 사용하는법은 아래 게시글에 정리해두었습니다)

https://raon-2.tistory.com/15

 

 

---

4. 마무리

DFS 방문처리를 visited와 같은 배열로 항상 따로 두어서 처리하는건줄 알았는데, DEPTH를 이용해서 저런 방식으로 dfs를 사용할 수 있다는 것을 알게 되었습니다.